Теорема Карпа – Липтона

В теории сложности теорема Карпа – Липтона утверждает, что если булева проблема выполнимости (SAT) может быть решена с помощью булевых схем с полиномиальным числом логических элементов, то

\Pi _{2}=\Sigma _{2}\,

и поэтому

{\mathsf {PH}}=\Sigma _{2}.\,

То есть, если мы предположим, что NP , класс недетерминированных задач с полиномиальным временем, может содержаться в классе неоднородной полиномиальной временной сложности P/poly , то это предположение подразумевает коллапс полиномиальной иерархии на ее втором уровне. Такой коллапс считается маловероятным, поэтому теоретики сложности обычно рассматривают эту теорему как свидетельство отсутствия схем полиномиального размера для SAT или других NP-полных задач. Доказательство того, что таких схем не существует, будет означать, что P ≠ NP . Поскольку P/poly содержит все проблемы, решаемые за полиномиальное рандомизированное время ( теорема Адлемана ), эта теорема также является свидетельством того, что использование рандомизации не приводит к алгоритмам с полиномиальным временем для NP-полных задач.

Теорема Карпа-Липтона названа в честь Ричарда М. Карпа и Ричарда Дж. Липтона , которые впервые доказали ее в 1980 году. (Их первоначальное доказательство свернуло PH на $\Sigma _{3}$ , но Майкл Сипсер улучшил его до $\Sigma _{2}$ .)

Варианты теоремы утверждают, что при том же предположении MA = AM и PH схлопывается в S ^П
₂ класс сложности. Возможны более строгие выводы, если PSPACE предполагается, что или некоторые другие классы сложности имеют схемы полиномиального размера; см . P/poly . Если предполагается, что NP является подмножеством BPP (которое является подмножеством P/poly), то полиномиальная иерархия схлопывается до BPP . ^{[ 1 ]} Если предполагается, что coNP является подмножеством NP/poly , то полиномиальная иерархия схлопывается до третьего уровня.

Интуиция

Предположим, что схемы полиномиального размера для SAT не только существуют, но и могут быть построены с помощью алгоритма с полиномиальным временем. Тогда это предположение подразумевает, что сама SAT может быть решена с помощью алгоритма с полиномиальным временем, который создает схему, а затем применяет ее. То есть эффективно построенные схемы для SAT приведут к более сильному коллапсу P = NP.

Предположение теоремы Карпа–Липтона о существовании таких схем более слабое. Но это все еще возможно для алгоритма в классе сложности $\Sigma _{2}$ угадать . правильную схему для SAT Класс сложности $\Sigma _{2}$ описывает проблемы формы

\exists x\forall y\;\psi (x,y)

где $\psi$ — любой предикат, вычислимый за полиномиальное время. Экзистенциальную мощность первого квантора в этом предикате можно использовать для угадывания правильной схемы для SAT, а универсальную мощность второго квантора можно использовать для проверки правильности схемы. Как только эта схема будет угадана и проверена, алгоритм в классе $\Sigma _{2}$ можно использовать его как подпрограмму для решения других задач.

Самосократимость

Чтобы понять доказательство Карпа – Липтона более подробно, мы рассмотрим задачу проверки того, является ли схема c правильной схемой для решения экземпляров SAT заданного размера, и покажем, что эта задача проверки схемы принадлежит к $\Pi _{1}$ . То есть, существует предикат V, вычислимый за полиномиальное время, такой, что c является корректной схемой тогда и только тогда, когда для всех полиномиально ограниченных z , V ( c , z ) истинно.

Схема c является правильной схемой для SAT, если она удовлетворяет двум свойствам:

Для каждой пары ( s , x ), где s — экземпляр SAT, а x — решение этого экземпляра, c ( s ) должно быть истинным.
Для каждого экземпляра s SAT, для которого c ( s ) истинно, s должно быть разрешимо.

Первое из этих двух свойств уже проявляется в виде задач на уроке. $\Pi _{1}$ . Для проверки второго свойства воспользуемся свойством самосократимости SAT.

Самосократимость описывает явление, заключающееся в том, что если мы сможем быстро проверить, разрешима ли задача SAT, мы сможем почти так же быстро найти явное решение для этой задачи. Чтобы найти решение экземпляра s , выберите одну из логических переменных x , которая является входными данными для s , и создайте два меньших экземпляра s ₀ и s ₁ , где s _i обозначает формулу, образованную путем замены x константой i . Как только эти два меньших экземпляра будут построены, примените тест на разрешимость к каждому из них. Если один из этих двух тестов покажет, что меньший экземпляр выполним, продолжайте решать этот пример, пока не будет получено полное решение.

Чтобы использовать самоприводимость для проверки второго свойства корректной схемы для SAT, перепишем его следующим образом:

Для каждого экземпляра s SAT, для которого c ( s ) истинно, описанная выше процедура саморедукции находит допустимое решение s .

Таким образом, мы можем протестировать в $\Pi _{1}$ является ли c допустимой схемой для решения SAT.

см. в разделе «Случайная самосократимость» Дополнительную информацию .

Доказательство теоремы Карпа–Липтона.

Теорема Карпа – Липтона может быть переформулирована как результат, касающийся булевых формул с полиномиально ограниченными кванторами. Проблемы в $\Pi _{2}$ описываются формулами этого типа с синтаксисом

\phi =\forall x\exists y\;\psi (x,y)

где $\psi$ является вычислимым за полиномиальное время предикатом. Теорема Карпа – Липтона утверждает, что формулы этого типа можно преобразовать за полиномиальное время в эквивалентную формулу, в которой кванторы появляются в противоположном порядке; такая формула принадлежит $\Sigma _{2}$ . Обратите внимание, что подформула

s(x)=\exists y\;\psi (x,y)

является экземпляром SAT. То есть, если c — допустимая схема для SAT, то эта подформула эквивалентна неквантованной формуле c ( s ( x )). Таким образом, полная формула для $\phi$ эквивалентно (в предположении существования допустимой схемы c ) формуле

\exists c\forall (x,z)\;V(c,z)\wedge c(s(x))\,

где V — формула, используемая для проверки того, что c действительно является допустимой схемой с использованием самосократимости, как описано выше. В этой эквивалентной формуле квантификаторы расположены в противоположном порядке по желанию. Таким образом, предположение Карпа–Липтона позволяет транспонировать порядок кванторов существования и всеобщности в формулах этого типа, показывая, что $\Sigma _{2}=\Pi _{2}.$ Повторение транспозиции позволяет упростить формулы с более глубокой вложенностью до формы, в которой они имеют один квантор существования, за которым следует один квантор всеобщности, показывая, что $PH=\Sigma _{2}.$

Еще одно доказательство и S ^П
₂

Предполагать ${\mathsf {NP}}\subseteq {\mathsf {P/poly}}$ . Следовательно, существует семейство схем $C_{n}$ который решает выполнимость на входе длины n . Используя самоприводимость, существует семейство схем $D_{n}$ который выводит удовлетворительное присваивание для истинных экземпляров.

Предположим, что L — это $\Pi _{2}$ набор

L=\{z:\forall x.\exists y.\phi (x,y,z)\}\,

С $\exists y.\phi (x,y,z)$ можно считать примером SAT (по теореме Кука-Левина ), существует схема $D_{n}$ , в зависимости от $n=|z|$ , такой, что формула, определяющая L, эквивалентна

\forall x.\phi (x,D_{n}(x,z),z)

( 1 )

Более того, схему можно угадать с помощью экзистенциальной количественной оценки:

\exists D.\forall x.\phi (x,D(x,z),z)

( 2 )

Очевидно, ( 1 ) влечет за собой ( 2 ). Если (1) неверно, то $\neg \exists y.\phi (x,y,z)$ . В этом случае ни одна схема D не может выдать задание, производящее $\phi (x,D(x,z),z)\;$ истинный.

Доказательство показало, что $\Pi _{2}$ набор $L$ находится в $\Sigma _{2}$ .

Более того, если $\Pi _{2}$ формула верна, то схема D будет работать против любого x . Если $\Pi _{2}$ формула ложна, то x, делающий формулу (1) ложной, будет работать против любой схемы. Это свойство означает более сильный коллапс, а именно S ^П
₂ класс сложности (т.е. $\Pi _{2}\subseteq {\mathsf {S}}_{2}^{P}\subseteq \Sigma _{2}$ ). Это заметил Сенгупта. ^{[ 2 ]}

AM = МА

Модификация ^{[ 3 ]} из приведенного выше доказательства дает

{\mathsf {NP}}\subseteq {\mathsf {P/poly}}\implies {\mathsf {AM}}={\mathsf {MA}}

(см. протокол Артура-Мерлина ).

Предположим, что L находится в AM , т.е.:

z\in L\implies \Pr \nolimits _{x}[\exists y.\phi (x,y,z)]\geq {\tfrac {2}{3}}

z\notin L\implies \Pr \nolimits _{x}[\exists y.\phi (x,y,z)]\leq {\tfrac {1}{3}}

и, как ранее, переписать $\exists y.\phi (x,y,z)$ используя схему $D_{n}$ который выводит удовлетворяющее присваивание, если оно существует:

z\in L\implies \Pr \nolimits _{x}[\phi (x,D_{n}(x,z),z)]\geq {\tfrac {2}{3}}

z\notin L\implies \Pr \nolimits _{x}[\phi (x,D_{n}(x,z),z)]\leq {\tfrac {1}{3}}

С $D_{n}$ можно предположить:

z\in L\implies \exists D.\Pr \nolimits _{x}[\phi (x,D(x,z),z)]\geq {\tfrac {2}{3}}

z\notin L\implies \forall D.\Pr \nolimits _{x}[\phi (x,D(x,z),z)]\leq {\tfrac {1}{3}}

что доказывает $L$ находится в меньшем классе MA .

Приложение к нижним границам схемы - теорема Каннана

Каннана Теорема ^{[ 4 ]} утверждает, что для любого фиксированного k существует язык $L$ в $\Sigma _{2}$ , которого нет в SIZE (n ^к) (Это утверждение отличается от $\Sigma _{2}\not \subseteq {\mathsf {P/poly}}$ , который в настоящее время открыт и утверждает, что существует один язык, которого нет в SIZE (n ^к) для любого k ). Это нижняя граница простой схемы .

Схема доказательства:

Существует язык $L\in \Sigma _{4}-{\mathsf {SIZE}}(n^{k})$ (в доказательстве используется техника диагонализации ). Рассмотрим два случая:

Если ${\mathsf {SAT}}\notin {\mathsf {P/poly}}$ затем ${\mathsf {SAT}}\notin {\mathsf {SIZE}}(n^{k})$ и теорема доказана.
Если ${\mathsf {SAT}}\in {\mathsf {P/poly}}$ , то по теореме Карпа–Липтона $\Sigma _{4}=\Sigma _{2}$ и поэтому $L\in \Sigma _{2}-{\mathsf {SIZE}}(n^{k})$ .

Более сильная версия теоремы Карпа – Липтона усиливает теорему Каннана следующим образом: для любого k существует язык $L\in {\mathsf {S}}_{2}^{P}-{\mathsf {SIZE}}(n^{k})$ .

Также известно, что ПП не содержится в ${\mathsf {SIZE}}(n^{k})$ , что было доказано Винодчандраном. ^{[ 5 ]} Доказательство: ^{[ 6 ]}

Если ${\mathsf {PP}}\not \subseteq {\mathsf {P/poly}}$ затем ${\mathsf {PP}}\not \subseteq {\mathsf {SIZE}}(n^{k})$ .
В противном случае, ${\mathsf {P^{\#P}}}\subseteq {\mathsf {P/poly}}$ . С

{\mathsf {P^{\#P}}}\supseteq {\mathsf {PP}}\supseteq {\mathsf {MA}}

(собственность МА )

{\mathsf {P^{\#P}}}\supseteq {\mathsf {PH}}\supseteq \Sigma _{2}\supseteq {\mathsf {MA}}

(по теореме Тоды и свойству МА)

{\mathsf {P^{\#P}}}={\mathsf {MA}}

(следует из предположения использования интерактивного протокола для постоянного, см. P/poly )

вложения являются равенствами, и мы получаем

{\mathsf {PP}}=\Sigma _{2}\not \subseteq {\mathsf {SIZE}}(n^{k})

по теореме Каннана.

Ссылки

^ С. Захос , Вероятностные квантификаторы и игры, 1988.
^ Цзинь И-Кай. $S_{2}^{P}\subseteq {\mathsf {ZPP}}^{\mathsf {NP}}$ [1] , раздел 6
^ В. Арвинд, Дж. Кёблер, У. Шенинг , Р. Шулер, Если NP имеет схемы полиномиального размера, то MA = AM
^ Каннан, Р. (1982). «Нижние границы размера схемы и несводимость к разреженным множествам». Информация и контроль . 55 (1–3): 40–56. дои : 10.1016/S0019-9958(82)90382-5 .
^ Н.В. Винодчандран, Заметка о сложности схемы ПП.
^ С. Ааронсон , Оракулы хитры, но не злонамеренны.

Карп, РМ ; Липтон, Р.Дж. (1980), «Некоторые связи между неоднородными и однородными классами сложности», Труды двенадцатого ежегодного симпозиума ACM по теории вычислений , стр. 302–309, doi : 10.1145/800141.804678 , S2CID 1458043 .

Карп, РМ ; Липтон, Р.Дж. (1982), «Машины Тьюринга, которые принимают советы», L'Enseignement Mathématique , 28 : 191–209, doi : 10.5169/seals-52237 .

[1] С. Захос , Вероятностные квантификаторы и игры, 1988.

[2] Цзинь И-Кай. $S_{2}^{P}\subseteq {\mathsf {ZPP}}^{\mathsf {NP}}$ [1] , раздел 6

[3] В. Арвинд, Дж. Кёблер, У. Шенинг , Р. Шулер, Если NP имеет схемы полиномиального размера, то MA = AM

[4] Каннан, Р. (1982). «Нижние границы размера схемы и несводимость к разреженным множествам». Информация и контроль . 55 (1–3): 40–56. дои : 10.1016/S0019-9958(82)90382-5 .

[5] Н.В. Винодчандран, Заметка о сложности схемы ПП.

[6] С. Ааронсон , Оракулы хитры, но не злонамеренны.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]