In complexity theory, the Karp–Lipton theorem states that if the Boolean satisfiability problem (SAT) can be solved by Boolean circuits with a polynomial number of logic gates, then That is, if we assume that NP, the class of nondeterministic polynomial time problems, can be contained in the non-uniform polynomial time complexity class P/poly, then this assumption implies the collapse of the 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.
Variants of the theorem state that, under the same assumption, MA = AM, and PH collapses to SP2 complexity class.
There are stronger conclusions possible if PSPACE, or some other complexity classes are assumed to have polynomial-sized circuits; see P/poly.
[1] If coNP is assumed to be subset of NP/poly, then the polynomial hierarchy collapses to its third level.
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 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
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.
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 s0 and s1 where si 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.
To use self-reducibility to check the second property of a correct circuit for SAT, we rewrite it as follows: Thus, we can test in
The Karp–Lipton theorem can be restated as a result about Boolean formulas with polynomially-bounded quantifiers.
That is, if c is a valid circuit for SAT, then this subformula is equivalent to the unquantified formula c(s(x)).
is equivalent (under the assumption that a valid circuit c exists) to the formula 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
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
that solves satisfiability on input of length n. Using self-reducibility, there exists a family of circuits
which outputs a satisfying assignment on true instances.
can be considered an instance of SAT (by Cook-Levin theorem), there exists a circuit
, such that the formula defining L is equivalent to Furthermore, the circuit can be guessed with existential quantification: Obviously (1) implies (2).
In this case, no circuit D can output an assignment making
This property means a stronger collapse, namely to SP2 complexity class (i.e.
Kannan's theorem[4] states that for any fixed k there exists a language
, which is currently open and states that there exists a single language that is not in SIZE(nk) for any k).