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
Contents
- Intuition
- Self reducibility
- Proof of KarpLipton theorem
- Another proof and S2P
- AM MA
- Application to circuit lower bounds Kannans theorem
- References
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 Karp–Lipton 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 Richard M. Karp and Richard J. Lipton, who first proved it in 1980. (Their original proof collapsed PH to
Variants of the theorem state that, under the same assumption, MA = AM, and PH collapses to SP
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. 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
where
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
The circuit c is a correct circuit for SAT if it satisfies two properties:
The first of these two properties is already in the form of problems in class
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. 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:
Thus, we can test in
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
where
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
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
Another proof and S2P
Assume
Suppose L is a
Since
Furthermore, the circuit can be guessed with existential quantification:
Obviously (1) implies (2). If (1) is false, then
The proof has shown that a
What more, if the
2 complexity class (i.e.
AM = MA
A modification of the above proof yields
(see Arthur–Merlin protocol).
Suppose that L is in AM, i.e.:
and as previously rewrite
Since
which proves
Application to circuit lower bounds – Kannan's theorem
Kannan's theorem states that for any fixed k there exists a language
Proof outline:
There exists a language
A stronger version of Karp–Lipton theorem strengthens Kannan's theorem to: for any k, there exists a language
It is also known that PP is not contained in