The Karp-Lipton TheoremKannan's TheoremThe Valiant-Vazirani TheoremStanford University — CS254: Computational Complexity Handout 6Luca Trevisan April 14, 2010Last revised 4/29/2010In this lecture we prove the Karp-Lipton theorem that if all NP problems have poly-nomial size circuits then the polynomial hierarchy collapses. A nice application is atheorem of Kannan, showing that, for every k, there are languages in Σ2requiringcircuits of size Ω(nk). The next result we wish to prove is that all approximate com-binatorial counting problem can be solved within the polynomial hierarchy. Beforeintroducing counting problems and the hashing techniques that will yield this result,we prove the Valiant-Vazirani theorem that solving SAT on instances with exactlyone satisfying assignment is as hard as solving SAT in general.1 The Karp-Lipton TheoremTheorem 1 (Karp-Lipton) If NP ⊆ SIZE(nO(1)) then Σ2= Π2and therefore thepolynomial hierarchy would collapse to its second level.Before proving the above theorem, we first show a result that contains some of theideas in the proof of the Karp-Lipton theorem.Lemma 2 If NP ⊆ SIZE(nO(1)) then for every polynomial time computable F (·, ·)and every polynomial p(·), there is a family of polynomial size circuits such thatC|x|(x) =(y : F (x, y) = 1 if such a y existsa sequence of zeroes if otherwiseProof: We define the circuits C1n, . . . , Cp(n)nas follows:Cin, on input x and bits b1, . . . , bi−1, outputs 1 if and only if there is a satisfyingassignment for F (x, y) = 1 where y1= b1, . . . , yi−1= bi−1, yi= 1.Also, each circuit realizes an NP computation, and so it can be built of polyno-mial size. Consider now the sequence b1= C1n(x), b2= C2n(b1, x), . . ., bp(n)=Cp(n)n(b1, . . . , bp(n)−1, x), as shown in the following picture:1x11ythere is ystarting with12x11ythere is y2y2x11y1bx11y2b1b1b2b. . .. . .there is ystarting with2b1there is ystarting withbb121123b0 or 1The reader should be able to convince himself that this is a satisfying assignment forF (x, y) = 1 if it is satisfiable, and a sequence of zeroes otherwise. We now prove the Karp-Lipton theorem.Proof: [Of Theorem 1] We will show that if NP ⊆ SIZE(nO(1)) then Π2⊆ Σ2. Bya result in a previous lecture, this implies that ∀k ≥ 2 Σk= Σ2.Let L ∈ Π2, then there is a polynomial p(·) and a polynomial-time computable F (·)such thatx ∈ L ↔ ∀y1.|y1| ≤ p(|x|)∃y2.|y2| ≤ p(|x|).F (x, y1, y2) = 1By using Lemma 2, we can show that, for every n, there is a circuit Cnof sizepolynomial in n such that for every x of length n and every y1, |y1| ≤ p(|x|),∃y2.|y2| ≤ p(|x|) ∧ F (x, y1, y2) = 1 if and only if F (x, y1, Cn(x, y1)) = 1Let q(n) be a polynomial upper bound to the size of Cn.So now we have that for inputs x of length n,x ∈ L ↔ ∃C.|C| ≤ q(n).∀y1.|y1| ≤ p(n).F (x, y1, C(x, y1)) = 1which shows that L is in Σ2. 2 Kannan’s TheoremAlthough it is open to prove that the polynomial hierarchy is not contained in P/poly,it is not hard to prove the following result.2Theorem 3 For every polynomial p(), there is a language L ∈ Σ3such that L 6∈SIZE(p(n)).Note that Theorem 3 is not saying that Σ36⊆ P/poly, because for that to be true wewould have to be able to construct a single language L such that for every polynomialp we have L 6∈ SIZE(p(n)), instead of constructing a different language for eachpolynomial. (This is an important difference: the time hierarchy theorem gives us,for every polynomial p(), a language L ∈ P such that L 6∈ DTIME(p(n)), but thisdoesn’t mean that P 6= P.)Kannan observed the following consequence of Theorem 3 and of the Karp-Liptontheorem.Theorem 4 For every polynomial p(), there is a language L ∈ Σ2such that L 6∈SIZE(p(n)).Proof: We consider two cases:• if 3SAT 6∈ SIZE(p(n)); then we are done because 3SAT ∈ NP ⊆ Σ2.• if 3SAT ∈ SIZE(p(n)), then NP ⊆ P/poly, so by the Karp-Lipton theorem wehave Σ3= Σ2, and the language L ∈ Σ3− SIZE(p(n)) given by Theorem 3 isin Σ2. 3 The Valiant-Vazirani TheoremIn this section we begin to discuss the proof of the following result, due to Valiantand Vazirani: suppose there is an algorithm for the satisfiability problem that alwaysfind a satisfying assignment for formulae that have exactly one satisfiable assignment(and behaves arbitrarily on other instances): then we can get an RP algorithm forthe general satisfiability problem, and so NP = RP.We prove the result by presenting a randomized reduction that given in input a CNFformula φ produces in output a polynomial number of formulae ψ0, . . . , ψn. If φ issatisfiable, then (with high probability) at least one of the ψiis satisfiable and hasexactly one satisfying assignment; if φ is not satisfiable, then (with probability one)all ψiare unsatisfiable.The idea for the reduction is the following. Suppose φ is a satisfiable formula with nvariables that has about 2ksatisfying assignments, and let h : {0, 1}n→ {0, 1}kbe a3hash function picked from a family of pairwise independent hash functions: then theaverage number of assignments x such that φ(x) is true and h(x) = (0, . . . , 0) is aboutone. Indeed, we can prove formally that with constant probability there is exactlyone such assignment,1and that there is CNF formula ψ (easily constructed from φand h) that is satisfied precisely by that assignment. By doing the above constructionfor values of k ranging from 0 to n, we obtain the desired reduction. Details follow.Definition 5 Let H be a family of functions of the form h : {0, 1}n→ {0, 1}m.We say that H is a family of pair-wise independent hash functions if for every twodifferent inputs x, y ∈ {0, 1}nand for every two possible outputs a, b ∈ {0, 1}mwehavePh∈H[h(x) = a ∧ h(y) = b] =122mAnother way to look at the definition is that for every x 6= y, when we pick h atrandom then the random variables h(x) and h(y) are independent and uniformlydistributed. In particular, for every x 6= y and for every a, b we havePh[h(x) =a|h(y) = b] =Ph[h(x) = a].For m vectors a1, . . . , am∈ {0, 1}mand m bits b1, . . . , bm, define ha1,...,am,b1,...,bm:{0, 1}n→ {0, 1}mas ha,b(x) = (a1·x+b1, . . . , am·x+bm) where a·x := Σiaiximod 2,and let HAF Fbe the family of functions defined this way. Then it is not hard to seethat HAF Fis a family of pairwise independent hash functions.1For technical reasons, it will be easier to prove that this is the case when picking a hash functionh : {0, 1}n→ {0,