Counting complexity

#P and PP: #P-completeness (counting SAT, permanent), PP-completeness, Toda's theorem, threshold languages, and approximate counting algorithms and schemes (Stockmeyer, Karp–Luby, Jerrum–Sinclair–Vigoda).

TheoremStockmeyer: approximate counting of #P functions in BPP^NP#●ready to prove

For every function \(f\) in \(\#P\) there are a decision problem \(O\) in NP, polynomials \(p_r\), \(p\) and \(q\) with natural-number coefficients, and polynomial-time computable functions \(\mathrm{nextQ}\) and \(\mathrm{final}\), each taking a bitstring and a list of query/answer pairs (bitstring, boolean), with \(\mathrm{nextQ}\) returning a bitstring and \(\mathrm{final}\) returning a natural number, such that the following holds. Let \(x\) and \(w\) be bitstrings with \(n = |w| \ge 1\), where \(|\cdot|\) denotes length, and put \(m = |x| + n\). For a bitstring \(r\) of length \(p_r(m)\), let \(E(r)\) be the output of the oracle computation that chooses queries with \(\mathrm{nextQ}\) and decides with \(\mathrm{final}\), run with oracle \(O\), query-length cap \(q(m)\) and \(p(m)\) adaptive queries on the bitstring encoding of the pair \((x, (r, w))\) from the empty history. Then \(f(x)/(1 + 1/n) \le E(r) \le f(x) \cdot (1 + 1/n)\), computed in the rationals, for at least two thirds of the \(2^{p_r(m)}\) bitstrings \(r\) of length \(p_r(m)\).

The bitstring \(w\) gives the precision \(n\) in unary; the number of random bits, the number of queries and the query-length cap are all polynomial in \(|x| + n\).

MetaMathlibExt.Complexity.KeyTheorems.Stockmeyer.stockmeyer_approximate_counting · 16 lines 
public theorem_wanted stockmeyer_approximate_counting :
    ∀ f : List Bool → ℕ, f ∈ SharpP →
      ∃ O : MetaMathlibExt.ComplexityTheory.DecisionProblem,
        O ∈ MetaMathlibExt.ComplexityTheory.NP ∧
      ∃ pRand p q : Polynomial ℕ,
      ∃ nextQ : List Bool × List (List Bool × Bool) → List Bool,
      ∃ final : List Bool × List (List Bool × Bool) → ℕ,
      IsPolyTime nextQ ∧ IsPolyTime final ∧
      ∀ (x : List Bool) (prec : List Bool), 1 ≤ prec.length →
        3 * Set.ncard {r : Fin (pRand.eval (x.length + prec.length)) → Bool |
          let E := evalOracle (q.eval (x.length + prec.length)) nextQ final O
            (MetaMathlibExt.BitstringEncoding.bitEncode (x, List.ofFn r, prec))
            (p.eval (x.length + prec.length)) []
          (f x : ℚ) / (1 + 1 / (prec.length : ℚ)) ≤ (E : ℚ) ∧
            (E : ℚ) ≤ (f x : ℚ) * (1 + 1 / (prec.length : ℚ))} ≥
          2 * 2 ^ (pRand.eval (x.length + prec.length))
Sources
  • L. J. Stockmeyer, "The complexity of approximate counting", Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC 1983), 118-126 (journal version in Information and Computation 1985).
Uses 14
Statement usesThe counting class \(\#P\) · Evaluation of an oracle machine with adaptive queries · Bitstring encodings · Decoding function of a bitstring encoding · Decoding inverts bitstring encoding · Encoding function of a bitstring encoding · Self-delimiting form of a bitstring · Parsing one self-delimiting block · Parsing a list of booleans into self-delimiting blocks · Bounded parsing of self-delimiting blocks · Complexity classes · Decision problems · Polynomial-time computable functions · The complexity class NP

TheoremToda's theorem: PH is contained in \(\mathsf{P}^{\#\mathsf{P}}\)#●ready to prove

Every decision problem in the polynomial hierarchy PH lies in \(\mathsf{P}^{\#\mathsf{P}}\), the class of decision problems decidable in polynomial time with a \(\#\mathsf{P}\) oracle.

public theorem_wanted toda :
    PH ⊆ PWithSharpP
Sources
  • S. Toda, "PP is as hard as the polynomial-time hierarchy", SIAM Journal on Computing 20 (1991), 865-877 (FOCS 1989).
Uses 4
Statement usesThe polynomial hierarchy · Polynomial time with a #P oracle · Complexity classes · Decision problems
2 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.