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