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

14

Я пытаюсь понять доказательство теоремы Карпа-Липтона, изложенное в книге «Вычислительная сложность: современный подход» (2009).

В частности, в этой книге говорится следующее:

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

Если NP P p o l y , то PH = Σ p 2 . Ppoly =Σ2p

Доказательство. По теореме 5.4, чтобы показать PH , достаточно показать, что Π p 2Σ p 2 и, в частности, достаточно показать, что Σ p 2 содержит Π p 2 -полный язык Π 2 SAT.=Σ2pΠ2pΣ2pΣ2pΠ2pΠ2

Теорема 5.4 утверждает, что

для каждого , если Σ p i = Π p i, то PH = Σ p i . То есть иерархия рушится до i-го уровня.i1Σip=ΠipΣip

Я не понимаю, как подразумевает Σ p 2 = Π p 2 .Π2pΣ2pΣ2p=Π2p

В качестве более общего вопроса: делает это для всякого , т.е. делает Π р яΣ р я означает , Σ р я = Π р я для всех I 1 ?iΠipΣipΣip=Πipi1

WardL
источник
Через некоторое время, если я правильно помню, мы пришли к смутным объяснения: «Если , то мы можем преобразовать формулу с кванторами . . . к одному с кванторами . . . , который мы можем использовать , чтобы преобразовать формулу из Е р 3 вида . . . . . . к одному из формы . . . . . . Π2pΣ2p......Σ3p............Σ2p
другое предположение / идея, математические операторы переключаются между включением подмножества и равенством (допустим, это часто встречается в теории сложности) Есть ли способ придерживаться / stdize / переформулировать в одном или другом? Fyi Karp-Lipton thm / wikipedia
vzn

Ответы:

8

LΣipL¯ΠipΣipΠipLΠip. Then L¯Σip and so L¯Πip by assumption, implying that LΣip. In other words, ΠipΣip, and so Σip=Πip.

Here's why LΣip iff L¯Πip. For concreteness, we take i=3. By definition, LΣ3p if for some P-time predicate T,

xL|y|<|x|O(1)|z|<|x|O(1)|w|<|x|O(1)T(x,y,z,w).
Similarly L¯Π3p if for some P-time predicate S,
xL¯|y|<|x|O(1)|z|<|x|O(1)|w|<|x|O(1)S(x,y,z,w).
However, these two statements are equivalent, as a simple invocation of de Morgan's laws shows, together with the fact that P is closed under complementation (take S=¬T).
Yuval Filmus
источник