Зафиксируем NP-полную задачу поиска, например форму поиска SAT. Поиск Левина предоставляет алгоритм L для решения X, который в некотором смысле является оптимальным. В частности, алгоритм таков: «Выполните все возможные программы P в соответствии друг с другом на входе x , как только некоторые P вернут ответ y, проверяет, правильно ли это». Это оптимально в том смысле, что дана программа P, которая решает X с временной сложностью t P , временная сложность t L ( n ) из L удовлетворяет
где - фиксированный полином, который зависит от точной модели вычислений
можно сформулировать несколько сильнее. А именно, для каждого M ⊂ { 0 , 1 } * и Q программырешающей X с посылом М во время т М Q ( п ) , временной сложность т M L ( п ) из L ограничивается входами в M удовлетворяет
где - фиксированный многочлен. Принципиальное отличие состоит в том, что t M Q ( n ) может быть, например, полиномиальным, даже если P ≠ N P
Очевидная «слабость» - большой фактор 2 | Q | в этом связан. Легко видеть, что если существует алгоритм, удовлетворяющий границе того же вида с 2 | Q | заменяется полиномом в | Q | то Р = Н Р . Это потому, что мы можем принять Q за программу, решающую некоторый данный экземпляр X путем жесткого кодирования ответа. Аналогично, если 2 | Q | можно заменить на субэкспоненциальную функцию | Q |тогда гипотеза экспоненциального времени нарушается. Однако ответ на следующий вопрос менее очевиден (для меня):
Предполагая гипотезу об экспоненциальном времени и другие известные гипотезы (например, невырожденность полиномиальной иерархии, существование односторонних функций), если необходимо, существует ли алгоритм решающий X st для каждого M ⊂ { 0 , 1 } ∗ и в программе решения X с посылом М во время т М Q ( п ) , временной сложность т М А ( п ) из А ограничена входы в M удовлетворяет
где полиномиальный, f субэкспоненциальный и g произвольный
Если ответ положительный, может ли быть полиномом? Какова скорость роста g (ясно, по крайней мере, экспоненциальный при ETH)? Если ответ отрицательный, может ли существовать многочлен f, если ETH неверен, но P ≠ N P ?