Изоморфизм Бермана-Хартманиса для NP

10

Используя модель real-RAM / BSS, мы имеем класс NP (где BSS - это модель компьютера Блума-Шуб-Смейла с операциями над реалами). У нас есть NP полные проблемы. Итак, вопрос в том, существует ли аналог гипотезы Бермана Хартманиса для класса NP ? Конечно, поставленный здесь вопрос зависит от модели - иными словами, поскольку в определении NP используется модель BSS, все ли NP- -полные задачи имеют та же структура с использованием модели BSS (это приближает гипотезу Бермана-Хартманиса для NP по реалам)?R R R RRRRRR

user3483902
источник

Ответы:

8

В зависимости от того, какую версию NPR вы используете, да или она открыта. Когда кто-то рассматривает машины BSS, которые используют только сложение и вычитание и только ветвление на равенстве, ответ - да. Если включить ветвление на < , я считаю, что оно все еще открыто, и то же самое, если разрешить умножения. Подробности см. В Cucker, Koiran и Matamala «Сложность и размерность», Inform. Proc. Lett. 1997

Джошуа Грохов
источник
1
Чувствительность к операциям имеет решающее значение для машины, например, если мы разрешаем только сложение и умножение для машины, наборы, распознаваемые машиной BSS, изменяются.
user3483902