18.405J Lecture 5: Toda's Theorem

18.405J/6.841J: Advanced Complexity Theory Lecture 5: Toda's Theorem 1 Overview In the last lecture we covered Valiant–Vazirani reduction and investigated the complexity of approximate counting. In this lecture we prove Toda’s Theorem: PH ⊆ P#P . 2 Toda’s Theorem Statement One can easily see from the definition of #P that NP, coNP ⊆ P#P . The question that is naturally to ask is: can we reduce a larger complexity class to #P? In [Tod91] Seinosuke Toda proved the following theorem. Theorem 1. It is true that PH ⊆ P#P . Moreover, the reduction queries an oracle from #P (say, #SAT) only once. 3 Randomized Reduction Let us recall the definition of ⊕SAT. L Definition 2. For every Boolean formula ϕ on n variables we say that x∈{0,1}n ϕ(x) is true iff ϕ(x) has an odd number of satisfying assignments. To put it another way, M X ϕ(x) ≡ ϕ(x) (mod 2). x∈{0,1}n x∈{0,1}n The language ⊕SAT consists of all the true formulae of the form L x∈{0,1}n ϕ(x). In this section we show how to reduce PH to ⊕SAT via a randomized reduction. In the next section we present an ingenious idea of Toda that allows us to derandomize the reduction at a cost of switching from ⊕SAT to #SAT. So, our goal in this section is the following theorem. Theorem 3. For every c ∈ N there exists a randomized algorithm that takes a quantified Boolean formula ϕ(x) withL n variables (x stands for the set of free variables), and a parameter m and outputs a formula y ψ(x, y) such that for every x M Pr[ϕ(x) = ψ(x, y)] ≥ 1 − 2−m . y The running time of the reduction is (nm)Oc (1) . 1 To prove this theorem we first need to establish some properties of 3.1 L -formulae. Properties of Parity-Quantified Formulae Let ϕ, ψ : {0, 1}n → {0, 1} be any Boolean functions. Let us denote #(ϕ) the number of satisfying assignments of ϕ. Then, one can easily build formulae ϕ + ψ and ϕ · ψ with O(n) variables such that • #(ϕ + ψ) = #(ϕ) + #(ψ); • #(ϕ · ψ) = #(ϕ) · #(ψ). L L Using this “arithmetic operations” one can easily show that if x ϕ(x) and y ψ(y) are parityquantified formulae with disjoint sets of variables, then their conjunction, disjunction and negation can be represented as parity-quantified formulae with only a constant blowup in size. This implies, for example, that ⊕P is closed under the complement. 3.2 Proof of Theorem 3 W.l.o.g. we can assume that ϕ(x) = ∃x1 ψ(x1 , x), where ψ is a quantified formula with c − 1 levels of alternation (note that x1 is a set of variables, not a single variable), since ⊕SAT is closed under taking negations. L Now we invoke the induction hypothesis and get a formula y τ (x1 , x, y) such that for every x1 , x we have M Pr[ τ (x1 , x, y) = ψ(x1 , x)] ≥ 1 − 2−(m+n+10) . y L Now by union bound we have that with probability at least 1 L − 2−(m+10) we have y τ (x1 , x, y) = ψ(x1 , x) for every x, x1 . In this case we have ϕ(x) = ∃x1 y τ (x1 , x, y), and it is only left to remove the outer quantifier. For this we use Valiant–Vazirani reduction. Let us first recall it in somewhat “abstract” setting. Theorem 4. There is a polynomial-time randomized algorithm that given 1n produces a Boolean formula α(x, y), where x is a vector of n variables, such that for any function β : {0, 1}n → {0, 1} we have • If ∃x β(x), then Pr[ M 1 (α(x, y) ∧ β(x))] ≥ ; 8n x,y • If ¬∃x β(x), then Pr[ M (α(x, y) ∧ β(x))] = 0; x,y 2 We invoke this Theorem N times (we will determine the exact value of N later) and get N formulae α1 (x1 , z), α2 (x1 , z), . . . , αN (x1 , z). We build the final formula as follows: N M _ (αi (x1 , z) ∧ i=1 x1 ,z M τ (x1 , x, y)). (1) y L Let us condition of the event that y τ (x1 , x, y) = ψ(x1 , x) for every x1 , x. Then we see that with probability at least (1 − 1/8n)N (1) is equal to ϕ(x). So, if we choose N = O(nm) we can make this probability at least 1 − 2−(m+10) . Thus, the total probability of failure is at most 2−(m+9)  2−m . It is left to observe that we can (and should!) transform (1) to a ⊕SAT instance using tricks from Section 3.1. 4 Derandomization In this section we show how to derandomize Theorem 3 at a cost of switching from ⊕SAT to #SAT. We can think about the reduction from the proof of Theorem 3 as a deterministic one that takes a string of random coins of size R. So, we have a polynomial-time deterministic reduction f (ϕ(x), r) such that • If ϕ(x), then for at least 0.99 fraction of r’s f (ϕ(x), r) ∈ ⊕SAT; • If ¬ϕ(x), then for at least 0.99 fraction of r’s f (ϕ(x), r) ∈ / ⊕SAT. We want to use a counting oracle to distinguish these two cases. For this we need the following gap-amplification Lemma. Lemma 5. There exists a polynomial-time deterministic reduction that given 1l and a ⊕SATformula ψ produces a Boolean formula γ such that • If ψ ∈ ⊕SAT, then #(γ) ≡ −1 (mod 2l ); • If ψ ∈ / ⊕SAT, then #(γ) ≡ 0 (mod 2l ). Let us first show how to finish the proof of Toda’s theorem assuming the Lemma. If we denote the reduction in the Lemma by T , then we can consider the following formula: X T (f (ϕ, r)). r If we choose l > R + 10, then for ϕ ∈ ⊕SAT and ϕ ∈ / SAT the ranges of possible values of this formula are disjoint. So, we can compute this sum using an oracle from #P (since T and f are polynomial-time deterministic reductions), and, thus, decide ϕ. So, it is left to prove the Lemma. For l = 1 there is nothing to prove: we can take the reduction to be the identity. By the inductive hypothesis suppose that #(γ 0 ) ≡ 0 or −1 (mod 2t ). We will show 3 how to switch from 2t to 22t . Namely, consider the formula γ = 4γ 03 + 3γ 04 (here by arithmetic operations we mean the tricks from Section 3.1). It turns out that it gives exactly what we need! If #(γ 0 ) ≡ 0 (mod 2t ), then #(γ) ≡ 0 (mod 22t ), but if #(γ 0 ) ≡ −1 (mod 2t ), then #(γ) ≡ −1 (mod 22t ). We repeat this process O(log l) times, and get the desired formula. It is left to observe that on each step the blow up in size is at most constant, so in total we have polynomial running time. References [Tod91] Seinosuke Toda. PP is as Hard as the Polynomial-Time Hierarchy. SIAM J. Comput., 20(5):865–877, 1991. 4