0
$\begingroup$

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

$\endgroup$
3

0

Your Answer

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