View source for Karp–Lipton theorem

{{short description|On collapse of the polynomial hierarchy if NP is in non-uniform polynomial time class}}
{{Hatnote|The notation used in this article is explained on the page [[Polynomial hierarchy|polynomial hierarchy]].}}
In [[Computational complexity theory|complexity theory]], the '''Karp–Lipton theorem''' states that if the [[Boolean satisfiability problem]] (SAT) can be solved by [[Boolean circuit]]s with a [[Polynomial|polynomial]] number of logic gates, then 

:<math>\Pi_2 = \Sigma_2 \,</math> and therefore <math>\mathsf{PH} = \Sigma_2. \,</math>

That is, if we assume that [[NP (complexity)|NP]], the class of nondeterministic polynomial time problems, can be contained in the [[Circuit complexity#Uniformity|non-uniform polynomial time]] complexity class P/poly, then this assumption implies the collapse of the [[Polynomial hierarchy|polynomial hierarchy]] at its second level. Such a collapse is believed unlikely, so the theorem is generally viewed by complexity theorists as evidence for the nonexistence of polynomial size circuits for SAT or for other NP-complete problems. A proof that such circuits do not exist would imply that P ≠ NP. As P/poly contains all problems solvable in randomized polynomial time (Adleman's theorem), the theorem is also evidence that the use of randomization does not lead to polynomial time algorithms for NP-complete problems.

The Karp–Lipton theorem is named after [[Biography:Richard M. Karp|Richard M. Karp]] and Richard J. Lipton, who first proved it in 1980. (Their original proof collapsed PH to <math>\Sigma_3</math>, but [[Biography:Michael Sipser|Michael Sipser]] improved it to <math>\Sigma_2</math>.)

Variants of the theorem state that, under the same assumption, '''[[MA (complexity)|MA]]''' = '''[[AM (complexity)|AM]]''', and '''PH''' collapses to '''[[S2P (complexity)|{{nowrap|S{{su|p=P|b=2}}}}]]''' complexity class. There are stronger conclusions possible if [[PSPACE]], or some other complexity classes are assumed to have polynomial-sized circuits; see P/poly. If NP is assumed to be a subset of BPP (which is a subset of P/poly), then the polynomial hierarchy collapses to [[BPP (complexity)|BPP]].<ref>[[Biography:Stathis Zachos|S. Zachos]], Probabilistic quantifiers and games, 1988</ref> If coNP is assumed to be subset of NP/poly, then the polynomial hierarchy collapses to its third level.

== Intuition ==
Suppose that polynomial sized circuits for SAT not only exist, but also that they could be constructed by a polynomial time algorithm. Then this supposition implies that SAT itself could be solved by a polynomial time algorithm that constructs the circuit and then applies it. That is, efficiently constructible circuits for SAT would lead to a stronger collapse, P = NP.

The assumption of the Karp–Lipton theorem, that these circuits exist, is weaker. But it is still possible for an algorithm in the complexity class <math>\Sigma_2</math> to ''guess'' a correct circuit for SAT. The complexity class <math>\Sigma_2</math> describes problems of the form
:<math>\exists x\forall y\;\psi(x,y)</math>
where <math>\psi</math> is any polynomial-time computable predicate. The existential power of the first quantifier in this predicate can be used to guess a correct circuit for SAT, and the universal power of the second quantifier can be used to verify that the circuit is correct. Once this circuit is guessed and verified, the algorithm in class <math>\Sigma_2</math> can use it as a subroutine for solving other problems.

== Self-reducibility ==

To understand the Karp–Lipton proof in more detail, we consider the problem of testing whether a circuit ''c'' is a correct circuit for solving SAT instances of a given size, and show that this circuit testing problem belongs to <math>\Pi_1</math>. That is, there exists a polynomial time computable predicate ''V'' such that ''c'' is a correct circuit if and only if, for all polynomially-bounded ''z'', ''V''(''c'',''z'') is true.

The circuit ''c'' is a correct circuit for SAT if it satisfies two properties:
*For every pair (''s'',''x'') where ''s'' is an instance of SAT and ''x'' is a solution to the instance, ''c''(''s'') must be true
*For every instance ''s'' of SAT for which ''c''(''s'') is true, ''s'' must be solvable.
The first of these two properties is already in the form of problems in class <math>\Pi_1</math>. To verify the second property, we use the ''self-reducibility'' property of SAT.

Self-reducibility describes the phenomenon that, if we can quickly test whether a SAT instance is solvable, we can almost as quickly find an explicit solution to the instance. To find a solution to an instance ''s'', choose one of the Boolean variables ''x'' that is input to ''s'', and make two smaller instances ''s''<sub>0</sub> and ''s''<sub>1</sub> where ''s''<sub>''i''</sub> denotes the formula formed by replacing ''x'' with the constant ''i''. Once these two smaller instances have been constructed, apply the test for solvability to each of them. If one of these two tests returns that the smaller instance is satisfiable, continue solving that instance until a complete solution has been derived.

To use self-reducibility to check the second property of a correct circuit for SAT, we rewrite it as follows:
*For every instance ''s'' of SAT for which ''c''(''s'') is true, the self-reduction procedure described above finds a valid solution to ''s''.

Thus, we can test in <math>\Pi_1</math> whether ''c'' is a valid circuit for solving SAT.

see [[Random self-reducibility]] for more information

== Proof of Karp–Lipton theorem ==
The Karp–Lipton theorem can be restated as a result about Boolean formulas with polynomially-bounded quantifiers. Problems in <math>\Pi_2</math> are described by formulas of this type, with the syntax
:<math>\phi = \forall x \exists y \; \psi(x, y)</math>
where <math>\psi</math> is a polynomial-time computable predicate. The Karp–Lipton theorem states that this type of formula can be transformed in polynomial time into an equivalent formula in which the quantifiers appear in the opposite order; such a formula belongs to <math>\Sigma_2</math>. Note that the subformula
:<math>s(x)=\exists y \; \psi(x, y)</math>
is an instance of SAT. That is, if ''c'' is a valid circuit for SAT, then this subformula is equivalent to the unquantified formula ''c''(''s''(''x'')). Therefore, the full formula for <math>\phi</math> is equivalent (under the assumption that a valid circuit ''c'' exists) to the formula
:<math>\exists c\forall (x,z)\;V(c,z)\wedge c(s(x)) \, </math>
where ''V'' is the formula used to verify that ''c'' really is a valid circuit using self-reducibility, as described above. This equivalent formula has its quantifiers in the opposite order, as desired. Therefore, the Karp–Lipton assumption allows us to transpose the order of existential and universal quantifiers in formulas of this type, showing that <math>\Sigma_2=\Pi_2.</math> Repeating the transposition allows formulas with deeper nesting to be simplified to a form in which they have a single existential quantifier followed by a single universal quantifier, showing that <math>PH=\Sigma_2.</math>

== Another proof and S{{su|p=P|b=2}}  ==
Assume <math>\mathsf{NP} \subseteq \mathsf{P/poly}</math>. Therefore, there exists a family of circuits <math>C_n</math> that solves satisfiability on input of length ''n''. Using self-reducibility, there exists a family of circuits <math>D_n</math> which outputs a satisfying assignment on true instances.

Suppose ''L'' is a <math>\Pi_2</math> set

:<math>L = \{z : \forall x. \exists y. \phi(x,y,z)\} \, </math>

Since <math>\exists y. \phi(x,y,z)</math> can be considered an instance of SAT (by Cook-Levin theorem), there exists a circuit <math>D_n</math>, depending on <math>n = |z|</math>, such that the formula defining ''L'' is equivalent to

{{NumBlk|:|<math>\forall x. \phi(x, D_n(x, z), z)</math>|{{EquationRef|1}}}}

Furthermore, the circuit can be guessed with existential quantification:

{{NumBlk|:|<math>\exists D. \forall x. \phi(x, D(x, z), z)</math>|{{EquationRef|2}}}}

Obviously ({{EquationNote|1}}) implies ({{EquationNote|2}}). If (1) is false, then <math>\neg \exists y. \phi(x,y,z)</math>. In this case, no circuit ''D'' can output an assignment making <math>\phi(x, D(x, z), z)\;</math> true.

The proof has shown that a <math>\Pi_2</math> set <math>L</math> is in <math>\Sigma_2</math>.

What's more, if the <math>\Pi_2</math> formula is true, then the circuit ''D'' will work against any ''x''. If the <math>\Pi_2</math> formula is false, then ''x'' making the formula (1) false will work against any circuit. This property means a stronger collapse, namely to '''[[S2P (complexity)|S{{su|p=P|b=2}}]]''' complexity class (i.e. <math>\Pi_2 \subseteq \mathsf{S}_2^P \subseteq \Sigma_2</math>). It was observed by Sengupta.<ref>Jin Yi-Cai. <math>S_2^P \subseteq \mathsf{ZPP}^{\mathsf{NP}}</math> [http://pages.cs.wisc.edu/~jyc/papers/S2-j.pdf], section 6</ref>

=== AM = MA ===
A modification<ref>V. Arvind, J. Köbler, [[Biography:Uwe Schöning|U. Schöning]], R. Schuler, [http://www.informatik.hu-berlin.de/forschung/gebiete/algorithmenII/Publikationen/Papers/ma-am.ps.gz If NP has Polynomial-Size Circuits, then MA = AM]</ref> of the above proof yields

:<math>\mathsf{NP} \subseteq \mathsf{P/poly} \implies \mathsf{AM} = \mathsf{MA}</math>

(see [[Arthur–Merlin protocol]]).

Suppose that ''L'' is in '''AM''', i.e.:
:<math>z \in L \implies \Pr\nolimits_x[\exists y. \phi(x,y,z)] \geq \tfrac{2}{3}</math>
:<math>z \notin L \implies \Pr\nolimits_x[\exists y. \phi(x,y,z)] \leq \tfrac{1}{3}</math>

and as previously rewrite <math>\exists y. \phi(x,y,z)</math> using the circuit <math>D_n</math> that outputs a satisfying assignment if it exists:
:<math>z \in L \implies \Pr\nolimits_x[\phi(x,D_n(x,z),z)] \geq \tfrac{2}{3}</math>
:<math>z \notin L \implies \Pr\nolimits_x[\phi(x,D_n(x,z),z)] \leq \tfrac{1}{3}</math>

Since <math>D_n</math> can be guessed:
:<math>z \in L \implies \exists D. \Pr\nolimits_x[\phi(x,D(x,z),z)] \geq \tfrac{2}{3}</math>
:<math>z \notin L \implies \forall D. \Pr\nolimits_x[\phi(x,D(x,z),z)] \leq \tfrac{1}{3}</math>

which proves <math>L</math> is in the smaller class '''MA'''.

== Application to circuit lower bounds – Kannan's theorem ==
Kannan's theorem<ref>{{cite journal
|first=R.
|last=Kannan
|title=Circuit-size lower bounds and non-reducibility to sparse sets
|journal=Information and Control
|volume=55
|pages=40–56
|year=1982
|issue=1–3
|doi=10.1016/S0019-9958(82)90382-5}}</ref> states that for any fixed ''k'' there exists a language <math>L</math> in <math>\Sigma_2</math>, which is not in '''SIZE'''(n<sup>k</sup>) (This is a different statement than <math>\Sigma_2 \not \subseteq \mathsf{P/poly}</math>, which is currently open and states that there exists a single language that is not in '''SIZE'''(n<sup>k</sup>) for any ''k''). It is a simple circuit lower bound.

Proof outline:

There exists a language <math>L \in \Sigma_4 - \mathsf{SIZE}(n^k)</math> (the proof uses [[Cantor's diagonal argument|diagonalization]] technique). Consider two cases:
* If <math>\mathsf{SAT} \notin \mathsf{P/poly}</math> then <math>\mathsf{SAT} \notin \mathsf{SIZE}(n^k)</math> and theorem is proved.
* If <math>\mathsf{SAT} \in \mathsf{P/poly}</math>, then by Karp–Lipton theorem, <math>\Sigma_4 = \Sigma_2</math> and therefore <math>L \in \Sigma_2 - \mathsf{SIZE}(n^k)</math>.

A stronger version of Karp–Lipton theorem strengthens Kannan's theorem to: for any ''k'', there exists a language <math>L \in \mathsf{S}_2^P - \mathsf{SIZE}(n^k)</math>.

It is also known that '''[[PP (complexity)|PP]]''' is not contained in <math>\mathsf{SIZE}(n^k)</math>, which was proved by Vinodchandran.<ref>N. V. Vinodchandran, [http://www.cse.unl.edu/~vinod/papers/pp.ps A note on the circuit complexity of PP]</ref> Proof:<ref>[[Biography:Scott Aaronson|S. Aaronson]], [http://www.scottaaronson.com/papers/subtle.pdf Oracles Are Subtle But Not Malicious]</ref>
* If <math>\mathsf{PP} \not \subseteq \mathsf{P/poly}</math> then <math>\mathsf{PP} \not \subseteq \mathsf{SIZE}(n^k)</math>.
* Otherwise, <math>\mathsf{P^{\#P}} \subseteq \mathsf{P/poly}</math>. Since

::<math>\mathsf{P^{\#P}} \supseteq \mathsf{PP} \supseteq \mathsf{MA}</math> (by property of [[MA (complexity)|MA]])
::<math>\mathsf{P^{\#P}} \supseteq \mathsf{PH} \supseteq \Sigma_2 \supseteq \mathsf{MA}</math> (by [[Toda's theorem]] and property of MA)
::<math>\mathsf{P^{\#P}} = \mathsf{MA}</math> (follows from assumption using interactive protocol for permanent, see P/poly)

: the containments are equalities and we get <math>\mathsf{PP} = \Sigma_2 \not \subseteq \mathsf{SIZE}(n^k)</math> by Kannan's theorem.

== References ==
<references/>

*{{citation
 | contribution = Some connections between nonuniform and uniform complexity classes
 | doi = 10.1145/800141.804678
 | pages = 302–309
 | title = Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing
 | year = 1980| s2cid = 1458043 | doi-access = free}}.

*{{citation
 | doi = 10.5169/seals-52237
 | pages = 191–209
 | title = Turing machines that take advice
 | volume = 28
 | journal = L'Enseignement Mathématique
 | year = 1982}}.

{{DEFAULTSORT:Karp-Lipton theorem}}
[[Category:Theorems in computational complexity theory]]

{{Sourceattribution|Karp–Lipton theorem}}