Prova do teorema de Karp-Lipton

14

Estou tentando entender a prova do teorema de Karp-Lipton, conforme declarado no livro "Complexidade computacional: uma abordagem moderna" (2009).

Em particular, este livro declara o seguinte:

Teorema de Karp-Lipton

Se NP , PH . Ppoeuy = Σ p 2 =Σ2p

Prova: pelo Teorema 5.4, para mostrar PH , basta mostrar que e, em particular, basta mostrar que contém -complete idioma \ Pi_2 SAT. Π p 2Σ p 2 Σ p 2 Π p 2 Π dois=Σ2pΠ2pΣ2pΣ2pΠ2pΠ2

O teorema 5.4 afirma que

para cada Eu1 , se ΣEup=ΠEup então PH = ΣEup . Ou seja, a hierarquia cai para o i-ésimo nível.

Não estou conseguindo entender como implica . Σ p 2 = Π p 2Π2pΣ2pΣ2p=Π2p

Como uma pergunta mais geral: isso vale para todo , isto é, implica para todos os ?EuΠEupΣEupΣEup=ΠEupEu1

WardL
fonte
Depois de um tempo, se bem me lembro, chegamos a uma explicação vaga: "Se , podemos transformar uma fórmula com quantificadores em uma com quantificadores , que podemos usar para transformar uma fórmula de da forma para uma das formas , o que o coloca em , o que provoca o colapso da hierarquia não estou certo de que eu entendo esse argumento completamente..Π2pΣ2p......Σ3p............Σ2p
WardL
outra sugestão / idéia, as declarações matemáticas alternam entre inclusão de subconjuntos e igualdade (admita que isso é comum na teoria da complexidade). existe uma maneira de manter / stdize / reformular em um ou outro? fyi Karp-Lipton thm / wikipedia
vzn 31/03

Respostas:

8

Lembre-se de que iff ˉ LΠ p i . Suponha agora que Σ p i¸ p i , e deixar L ¸ p i . Então ˉ LΣ p i e assim ˉ L¸ p i por hipótese, o que implica que L Σ p i . Em outras palavras, Π p iΣ p i , e assimeuΣEupeu¯ΠEupΣEupΠEupeuΠEupeu¯ΣEupeu¯ΠEupeuΣEupΠEupΣEup .ΣEup=ΠEup

Aqui está o porquê sse ˉ L¸ p i . Para concretude, tomamos i = 3 . Por definição, L Σ p 3 , se por algum P-time predicado T , x L | y | < | x | O ( 1 )| z | < | x | O ( 1 )euΣEupeu¯ΠEupEu=3euΣ3pT Da mesma forma ˉ L¸ p 3 , se por algum tempo-P predicado S , x ˉ G| y | < | x | O ( 1 )| z | < | x | O

xeu|y|<|x|O(1)|z|<|x|O(1)|W|<|x|O(1)T(x,y,z,W).
eu¯Π3pS No entanto, essas duas afirmações são equivalentes, como mostra uma simples invocação das leis de Morgan, juntamente com o fato de P ser fechado sob complementação (vejaS=¬T).
xeu¯|y|<|x|O(1)|z|<|x|O(1)|W|<|x|O(1)S(x,y,z,W).
S=¬T
Yuval Filmus
fonte