Я пытаюсь понять доказательство теоремы Карпа-Липтона, изложенное в книге «Вычислительная сложность: современный подход» (2009).
В частности, в этой книге говорится следующее:
Теорема Карпа-Липтона
Если NP P ∖ p o l y , то PH = Σ p 2 .
Доказательство. По теореме 5.4, чтобы показать PH , достаточно показать, что Π p 2 ⊆ Σ p 2 и, в частности, достаточно показать, что Σ p 2 содержит Π p 2 -полный язык Π 2 SAT.
Теорема 5.4 утверждает, что
для каждого , если Σ p i = Π p i, то PH = Σ p i . То есть иерархия рушится до i-го уровня.
Я не понимаю, как подразумевает Σ p 2 = Π p 2 .
В качестве более общего вопроса: делает это для всякого , т.е. делает Π р я ⊆ Σ р я означает , Σ р я = Π р я для всех I ≥ 1 ?
Ответы:
Here's whyL∈Σpi iff L¯∈Πpi . For concreteness, we take i=3 . By definition, L∈Σp3 if for some P-time predicate T ,
источник