Karp-Lipton theorem

From Wikipedia, the free encyclopedia

This article or section does not cite its references or sources.
Please help improve this article by introducing appropriate citations. (help, get involved!) This article has been tagged since November 2006.

The Karp-Lipton theorem in complexity theory states that if SAT has a polynomial size circuit, then

$\Pi_2 \,$ = $\Sigma_2 \,$ and therefore $\mathrm{PH} \,$ = $\Sigma_2 \,$ .

[edit] Proof of Karp-Lipton theorem

It is a well-known result that $\forall\exists\mathrm{SAT}$ is $\Pi_2\,$ -hard. Thus, if we can show that $\forall\exists\mathrm{SAT}\in\Sigma_2$ , it follows that $\Pi_2\subseteq\Sigma_2$ . By the definition of $\Sigma_2\,$ , we just need to find a polynomial time algorithm, $V\,$ so that

$\phi\in\forall\exists\mathrm{SAT}\Leftrightarrow\exists c\forall x\; V(\phi,x,c)=1$

Let the algorithm $\mathrm{V} \,$ , be defined as follows:

On input < The self-reducability property of SAT allows us to use the circuit to generate the satisfying assignment efficiently. The idea is to first ask the circuit if $\phi\,$ is satisfiable. If the circuit says 'yes', we then ask if $\phi\,$ with the first variable assigned to true is satisfiable. If it is, we can conclude that $x_1 = T\,$ in the satisfying assignment and set it as such. If it is not, we can then conclude that $x_1 = F\,$ in the satisfying assignment. Continuing this way for each variable of $\phi\,$ , we reduce the size of the variables by 1 at each step and ultimately generate the satisfying assignment.

To show that the algorithm $\mathrm{V} \,$ in fact satisfies the double implication, there are two cases to consider:

If $\phi \,$ is true, we can let $c\,$ be the concatenation of circuits for $\mathrm{SAT}\,$ . Such a $c\,$ exists and is polynomial in the length of $\psi\,$ by the hypothesis that $\mathrm{SAT}\,$ has a polynomial size circuit. Then for any $x\,$ , $c\,$ will correctly calculate a satisfying assignment for $\psi(x,\cdot)\,$ , which exists since $\phi\,$ is true. In other words, $\exists c\forall x \;V(\phi,x,c)=1$ .
If $\phi \,$ is false, $\exists x\forall y\;\neg\psi(x,y)$ . Let $x_0\,$ be such an $x\,$ . Then when we run $V\,$ on $\phi\,$ , $x_0\,$ , and any input $c\,$ , $V\,$ will reject in the second step by our choice of $x_0\,$ . In other words, $\forall c\exists x\;V(\phi,x,c)=0$ , which is equivalent to $\neg\left(\exists c\forall x\;V(\phi,x,c)=1\right)$ .

Taken together, we have that

$\phi\in\forall\exists\mathrm{SAT}\Leftrightarrow\exists c\forall x\;V(\phi,x,c)=1$ and $\Pi_2 \subseteq\Sigma_2 \,$ .

As shown above, $\Pi_2 \subseteq\Sigma_2 \,$ so for any language, $L\,$ , $L \in \Pi_2 \implies L \in \Sigma_2$ .

Therefore,

$M \in \Sigma_2 \implies \overline{M} \in \Pi_2 \implies \overline{M} \in \Sigma_2 \implies M \in \Pi_2$

Then,

$\Sigma_2 \subseteq\Pi_2 \,$ and $\Pi_2 \subseteq\Sigma_2 \,$

Therefore $\Sigma_2 = \Pi_2 \,$ .

Now that we have shown that $\Sigma_2 = \Pi_2 \,$ , we can show that $PH = \Sigma_2 \,$ . That is, the entire polynomial hierarchy collapses to $\Sigma_2\,$ .

To show this, we can write the quantifiers of $\,\Sigma_n$ as follows:

$\exists \forall \exists \forall \dots Q_{n-2} Q_{n-1} Q_n \,$

where $Q_{i}\,$ represents the quantifier at the $i^{th}\,$ position, and $Q_n = Q_{n-2}\,$ . Making use of the result $\Sigma_2 = \Pi_2 \,$ proved above, we can swap $Q_{n}\,$ and $Q_{n-1}\,$ , yielding:

$\exists \forall \exists \forall \dots Q_{n-2} Q_{n} Q_{n-1} \,$

which we can reduce to:

$\exists \forall \exists \forall \dots Q_{n-2} Q_{n-1} \,$

because $Q_n = Q_{n-2}\,$ . Thus we have just reduced $\Sigma_n\,$ to $\Sigma_{n-1}\,$ . By a simple induction argument, it is easy to see that this can be repeatedly applied to reduce $\Sigma_n\,$ to $\Sigma_{2}\,$ , and that $\Pi_n\,$ can also be reduced in this manner. Since the complexity class PH is defined as $\cup_{n=1}^\infty \Sigma_n$ and we have shown that every class in this union can be reduced to $\Sigma_{2}\,$ , we have shown that $PH = \Sigma_2 \,$