The Wikipedia article about the Karp-Lipton theorem ($NP\subseteq P/poly$ implies $\Sigma_2=\Pi_2$), says the following:

The Karp–Lipton theorem is named after Richard M. Karp and Richard J. Lipton, who first proved it in 1980. (Their original proof collapsed PH to $\Sigma_3$, but Michael Sipser improved it to $\Sigma_2$)

However, there's no reference to where Sipser proved this improvement.

Where can I find Sipser's improved proof of Karp-Lipton theorem?

Edit: to be clear, I'm looking for the original reference, not other resources explaining the result



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.