Оптимальные NP-решатели

12

Зафиксируем NP-полную задачу поиска, например форму поиска SAT. Поиск Левина предоставляет алгоритм L для решения X, который в некотором смысле является оптимальным. В частности, алгоритм таков: «Выполните все возможные программы P в соответствии друг с другом на входе x , как только некоторые P вернут ответ y, проверяет, правильно ли это». Это оптимально в том смысле, что дана программа P, которая решает X с временной сложностью t PX{0,1}×{0,1}LXPxPyPX , временная сложность t L ( n ) из L удовлетворяетtP(n)tL(n)L

tL(n)<2|P|p(tP(n))

где - фиксированный полином, который зависит от точной модели вычисленийp

можно сформулировать несколько сильнее. А именно, для каждого M { 0 , 1 } * и Q программырешающей X с посылом М во время т М Q ( п ) , временной сложность т M L ( п ) из L ограничивается входами в M удовлетворяетLM{0,1}QXMtQM(n)tLM(n)LM

tLM(n)<2|Q|q(n,tQM(n))

где - фиксированный многочлен. Принципиальное отличие состоит в том, что t M Q ( n ) может быть, например, полиномиальным, даже если P N PqtQM(n)PNP

Очевидная «слабость» - большой фактор 2 | Q | в этом связан. Легко видеть, что если существует алгоритм, удовлетворяющий границе того же вида с 2 | Q | заменяется полиномом в | Q | то Р = Н Р . Это потому, что мы можем принять Q за программу, решающую некоторый данный экземпляр X путем жесткого кодирования ответа. Аналогично, если 2 | Q | можно заменить на субэкспоненциальную функцию | Q |L2|Q|2|Q||Q|P=NPQX2|Q||Q|тогда гипотеза экспоненциального времени нарушается. Однако ответ на следующий вопрос менее очевиден (для меня):

Предполагая гипотезу об экспоненциальном времени и другие известные гипотезы (например, невырожденность полиномиальной иерархии, существование односторонних функций), если необходимо, существует ли алгоритм решающий X st для каждого M { 0 , 1 } и в программе решения X с посылом М во время т М Q ( п ) , временной сложность т М А ( п ) из А ограничена входы в M удовлетворяетAXM{0,1}QXMtQM(n)tAM(n)AM

tAM(n)<f(|Q|)q(n,tQM(n))+g(|Q|)

где полиномиальный, f субэкспоненциальный и g произвольныйqfg

Если ответ положительный, может ли быть полиномом? Какова скорость роста g (ясно, по крайней мере, экспоненциальный при ETH)? Если ответ отрицательный, может ли существовать многочлен f, если ETH неверен, но P N P ?fgfPNP

Ванесса
источник

Ответы:

12

Рассмотрим следующий алгоритм (вариант алгоритма Левина):

n

Остановитесь, когда один из алгоритмов найдет решение.

xn

  • QnO(ntQM(n))poly(n)

  • Qnn<2|Q|2nO(1)=22O(|Q|)

tAM(n)poly(n)tQM(n)+22O(|Q|).

f(n)g(n)ng(n)nf(n)n

Юрий
источник
2|Q|tQM(2|Q|)