I am trying to understand the proof of the Karp-Lipton theorem as stated in the

ID: 647423 • Letter: I

Question

I am trying to understand the proof of the Karp-Lipton theorem as stated in the book "Computational Complexity: A modern approach" (2009).

In particular, this book states the following:

Karp-Lipton theorem

If NP ? P?poly, then PH =?p2.

Proof: By Theorem 5.4, to show PH =?p2, it suffices to show that ?p2??p2 and in particular it suffices to show that ?p2 contains the ?p2-complete language ?2SAT.

Theorem 5.4 states that

for every i?1, if ?pi=?pi then PH = ?pi. That is, the hierarchy collapses to the ith level.

I am failing to understand how ?p2??p2 implies ?p2=?p2.

As a more general question: does this hold for every i, i.e. does ?pi??pi imply ?pi=?pi for all i?1?

Explanation / Answer

Recall that L??pi iff L

Navigate

I am trying to understand the point of Odata and when it would make sense. Right

I am trying to understand this code and see what each line does in this program

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

I am trying to understand the proof of the Karp-Lipton theorem as stated in the

Question

Explanation / Answer

Related Questions

Navigate