5 Randomness, counting, and the polynomial hierarchy
This chapter covers probabilistic polynomial time, the polynomial hierarchy, and counting classes. A probabilistic machine is a nondeterministic machine whose choice bits are uniformly random and which is observed at a fixed clock; \(\mathsf{BPP}\), \(\mathsf{RP}\), \(\mathsf{coRP}\), \(\mathsf{ZPP}\), and \(\mathsf{PP}\) are defined from its acceptance probability, and \(\# \mathsf{P}\) from accepting leaves of the computation tree, a different count when paths halt early. Formalized results include the class definitions and elementary containments, the Sipser–Lautemann theorem, \(\mathsf{PH} \subseteq \mathsf{PSPACE}\), \(\mathsf{PP} \subseteq \mathsf{PSPACE}\) (hence \(\mathsf{BPP} \subseteq \mathsf{PSPACE}\)), and Stockmeyer-style relative approximate counting with pairwise-independent hashing, stated for a fixed finite set and a uniformly random seed (no oracle machine is involved). The main open directions are the oracle characterization of the hierarchy, the closure properties of \(\mathsf{PP}\) through \(\mathsf{GapP}\), and Toda’s theorem.
5.1 Randomized classes
The acceptance probability \(\mathrm{acceptProb}_N(x, T)\) of a machine \(N\) is the fraction of the \(2^T\) choice sequences of length \(T\) along which the trace of \(N\) on \(x\) after \(T\) steps is in the halting state with output cell \(1\) equal to \(1\) (NTM.acceptProb, defined in the chapter on machine models). A path that halts after \(t {\lt} T\) steps is counted once for each of its \(2^{T - t}\) extensions. The finite probability toolkit used below is developed in the chapter on encodings: event probability, the bound \(2^{-k}\) on majority failure over \(12k + 1\) independent blocks, the invariance of acceptance probability under enlarging a clock by which every path has halted, and the repetition machine NTM.repeatAtTime that lifts majority amplification to machines. Adleman’s theorem \(\mathsf{BPP} \subseteq \mathsf{P/poly}\) (Complexity.BPP_subset_PPoly) is in the chapter on circuits.
Let \(N\) be a machine, \(L\) a language, \(T \colon \mathbb {N} \to \mathbb {N}\) a clock, and \(c\) a rational. \(N\) accepts \(L\) with probability at least \(c\) at clock \(T\) if \(\mathrm{acceptProb}_N(x, T(|x|)) \ge c\) for every \(x \in L\), and \(N\) accepts non-members with probability at most \(c\) at clock \(T\) if \(\mathrm{acceptProb}_N(x, T(|x|)) \le c\) for every \(x \notin L\). \(N\) is probabilistic polynomial-time if there are \(f\) and \(d\) with \(f = O(n^d)\) such that every trace of \(N\) on every input \(x\) has halted after \(f(|x|)\) steps.
\(\mathsf{BPTIME}(T)\) is the set of languages \(L\) for which there are a machine \(N\) (with any number of work tapes) and \(f = O(T)\) such that every path halts within \(f(|x|)\) steps, \(\mathrm{acceptProb}_N(x, f(|x|)) \ge 2/3\) for \(x \in L\), and \(\mathrm{acceptProb}_N(x, f(|x|)) \le 1/3\) for \(x \notin L\). \(\mathsf{BPP} = \bigcup _k \mathsf{BPTIME}(n^k)\).
\(\mathsf{RTIME}(T)\) is defined like \(\mathsf{BPTIME}(T)\) with acceptance probability at least \(1/2\) on \(x \in L\) and at most \(0\), that is equal to \(0\), on \(x \notin L\). \(\mathsf{RP} = \bigcup _k \mathsf{RTIME}(n^k)\) and \(\mathsf{coRP} = \{ L : \overline{L} \in \mathsf{RP}\} \).
\(\mathsf{ZPP} = \mathsf{RP} \cap \mathsf{coRP}\). The Las Vegas characterization is a separate planned node (Theorem 160); the library has only fixed-clock probabilistic semantics.
\(\mathsf{PPTIME}(T)\) is the set of languages \(L\) for which there are a machine \(N\) and \(f = O(T)\) such that every path halts within \(f(|x|)\) steps and \(x \in L \iff \mathrm{acceptProb}_N(x, f(|x|)) {\gt} 1/2\). \(\mathsf{PP} = \bigcup _k \mathsf{PPTIME}(n^k)\).
For every \(T\), \(\mathsf{DTIME}(T) \subseteq \mathsf{BPTIME}(T) \subseteq \mathsf{PPTIME}(T)\) and \(\mathsf{RTIME}(T) \subseteq \mathsf{NTIME}(T)\). Consequently \(\mathsf{P} \subseteq \mathsf{BPP} \subseteq \mathsf{PP}\); \(\mathsf{RP} \subseteq \mathsf{NP}\); \(\mathsf{ZPP} \subseteq \mathsf{RP}\), \(\mathsf{ZPP} \subseteq \mathsf{coRP}\), and \(\mathsf{ZPP} \subseteq \mathsf{NP}\); and \(\mathsf{RP}, \mathsf{ZPP} \subseteq \mathsf{NEXP}\).
A deterministic machine viewed as probabilistic has the same trace on every choice sequence, so it accepts with probability \(1\) or \(0\). Since \(2/3 {\gt} 1/2 {\gt} 1/3\), bounded error implies unbounded error with the same machine and clock. A positive acceptance probability exhibits an accepting path, and probability \(0\) excludes one, so the same machine witnesses \(\mathsf{RTIME}(T) \subseteq \mathsf{NTIME}(T)\). The \(\mathsf{ZPP}\) inclusions are immediate from \(\mathsf{ZPP} = \mathsf{RP} \cap \mathsf{coRP}\), and the \(\mathsf{NEXP}\) inclusions compose with \(\mathsf{NP} \subseteq \mathsf{NEXP}\).
\(\mathsf{P} \subseteq \mathsf{RP} \cap \mathsf{coRP} = \mathsf{ZPP}\).
A deterministic decider accepts yes-instances with probability \(1\) and no-instances with probability \(0\), so \(\mathsf{P} \subseteq \mathsf{RP}\); closure of \(\mathsf{P}\) under complement gives \(\mathsf{P} \subseteq \mathsf{coRP}\).
If \(L \in \mathsf{BPP}\) then \(\overline{L} \in \mathsf{BPP}\).
Run the probabilistic machine and output \(1\) exactly when it does not halt with output \(1\). Since every path has halted by the clock, this exchanges acceptance probability \(p\) with \(1 - p\); the extra steps that rewind the output head and rewrite the verdict keep the clock \(O(f)\), and acceptance probability does not change once every path has halted. (The library’s proof of Sipser–Lautemann does not need this; it proves the \(\Pi ^p_2\) half directly.)
For every \(L \in \mathsf{BPP}\) and every polynomial \(q\) there is a polynomial-time probabilistic machine, all of whose paths halt within its clock, that accepts every \(x \in L\) with probability at least \(1 - 2^{-q(|x|)}\) and every \(x \notin L\) with probability at most \(2^{-q(|x|)}\).
The repetition machine NTM.repeatAtTime with \(12s + 1\) runs already reaches error \(2^{-s}\) (NTM.repeatAtTime_acceptProb_ge_one_sub_two_pow, NTM.repeatAtTime_acceptProb_le_two_pow), but it fixes the repetition count and the clock in advance. The remaining work is a variant that computes \(q(|x|)\) and the clock from the input before repeating, or a padding argument that reduces to a fixed count per input length.
\(L \in \mathsf{coRP}\) if and only if some polynomial-time probabilistic machine, all of whose paths halt within its clock, accepts every \(x \in L\) with probability \(1\) and every \(x \notin L\) with probability at most \(1/2\).
Complement the verdict of an \(\mathsf{RP}\) machine for \(\overline{L}\) (output \(1\) exactly when it does not output \(1\)), and conversely.
\(\mathsf{ZPP}\) equals the class of languages decided by a polynomial-time probabilistic machine that outputs \(1\), \(0\), or “don’t know”, is never wrong, and says “don’t know” with probability at most \(1/2\); and it equals the class decided with zero error in expected polynomial time.
Run the \(\mathsf{RP}\) and \(\mathsf{coRP}\) machines and answer when one of them is conclusive; the first equality is also planned as Theorem 94. Neither the three-valued output convention nor an expected-time model is defined yet, and the expected-time semantics must be kept separate from the strict all-paths clock: a machine that is always correct and halts within a polynomial bound on every random string can be run on a fixed random string, so it decides a language in \(\mathsf{P}\).
5.2 The polynomial hierarchy
For a polynomial \(p \in \mathbb {N}[X]\) and a language \(L'\), let \(\exists ^p L' = \{ x : \exists w\ (|w| \le p(|x|) \wedge \langle x, w \rangle \in L')\} \) and \(\forall ^p L' = \{ x : \forall w\ (|w| \le p(|x|) \Rightarrow \langle x, w \rangle \in L')\} \), where \(\langle \cdot , \cdot \rangle \) is the library’s pairing. For a class \(\mathcal{C}\), let \(\exists \mathcal{C}\) be the set of languages \(\exists ^p L'\) with \(p\) a polynomial and \(L' \in \mathcal{C}\), and similarly \(\forall \mathcal{C}\). Then \(\Sigma ^p_0 = \mathsf{P}\), \(\Pi ^p_k = \{ L : \overline{L} \in \Sigma ^p_k\} \), \(\Sigma ^p_{k+1} = \exists \Pi ^p_k\), and \(\mathsf{PH} = \bigcup _k \Sigma ^p_k\).
Complementation exchanges the quantifiers: \(\overline{\exists ^p L'} = \forall ^p \overline{L'}\) and \(\overline{\forall ^p L'} = \exists ^p \overline{L'}\), and at the level of classes the complement class of \(\exists \mathcal{C}\) is \(\forall \{ L : \overline{L} \in \mathcal{C}\} \) and dually. Since \(\mathsf{P}\) is closed under complement, \(\Pi ^p_0 = \mathsf{P}\); and \(\Sigma ^p_{k+1} = \exists \Pi ^p_k\), \(\Pi ^p_{k+1} = \forall \Sigma ^p_k\), \(\Sigma ^p_1 = \exists \mathsf{P}\), and \(\Pi ^p_1 = \forall \mathsf{P}\). Moreover \(\mathsf{P} \subseteq \exists \mathsf{P}\) and \(\mathsf{P} \subseteq \forall \mathsf{P}\), and for every \(k\), \(\Sigma ^p_k \subseteq \Sigma ^p_{k+1}\), \(\Pi ^p_k \subseteq \Pi ^p_{k+1}\), and \(\Sigma ^p_k \subseteq \mathsf{PH}\); in particular \(\mathsf{P} \subseteq \mathsf{PH}\).
The complement of a bounded existential is the bounded universal of the complement, and \(\mathsf{P}\) is closed under complement. The two level inclusions are proved together by induction, using monotonicity of \(\exists \) and \(\forall \) in the class; the base case uses the zero witness bound, under which the only witness is the empty string, and the fact that the first projection of a pair is in \(\mathsf{FP}\).
If \(\Sigma ^p_k = \Pi ^p_k\) for some \(k \ge 1\), then \(\mathsf{PH} = \Sigma ^p_k\). In particular, if \(\mathsf{P} = \mathsf{NP}\) then \(\mathsf{PH} = \mathsf{P}\).
Adjacent existential quantifiers merge into one by pairing their witnesses, so \(\exists \Sigma ^p_k = \Sigma ^p_k\); then induct on the level. The special case uses \(\mathsf{NP} = \Sigma ^p_1\) and \(\mathsf{P} = \mathsf{NP} \Rightarrow \mathsf{NP} = \mathsf{coNP}\).
For every \(k\), \(\Sigma ^p_{k+1} = \mathsf{NP}^{\Sigma ^p_k}\), where \(\mathsf{NP}^{\mathcal{C}}\) is the class of languages decided in polynomial time by a nondeterministic oracle machine with an oracle in \(\mathcal{C}\).
The library has deterministic Boolean-oracle machines but no nondeterministic oracle machines or relativized classes yet, and the result depends on the exact query model. Given those, guess the query answers together with \(\Sigma ^p_k\) certificates for the positive answers and \(\Pi ^p_k\) certificates for the negative ones.
5.3 The Sipser–Lautemann theorem
For \(E \subseteq \{ 0,1\} ^m\), say shifts \(u_1, \dots , u_t \in \{ 0,1\} ^m\) cover \(E\) if every \(r \in \{ 0,1\} ^m\) has some \(i\) with \(r \oplus u_i \in E\). If \(\Pr [\overline{E}] \le 2^{-k}\) and \(m {\lt} kt\), some \(t\) shifts cover \(E\). If \(\Pr [E] \le 2^{-k}\) and \(t {\lt} 2^k\), no \(t\) shifts cover \(E\).
Shifting is a measure-preserving involution of the seed space. For existence, the shift tuples that fail to cover a fixed seed number \(|\overline{E}|^t\), and a union bound over the \(2^m\) seeds leaves a covering tuple. For non-existence, the \(t\) shifted copies of \(E\) have total size \(t|E| {\lt} 2^m\).
Let \(N\) accept every \(x \in L\) with probability at least \(2/3\) and every \(x \notin L\) with probability at most \(1/3\) at a clock \(f\) (no halting assumption is needed here). For \(n = |x|\) let \(R = 12(f(n) + 11) + 1\) be the number of trials, \(\ell = R f(n)\) the amplified seed length, and \(E_x \subseteq \{ 0,1\} ^{\ell }\) the set of seeds on which a strict majority of the \(R\) runs of \(N\) on \(x\), each for \(f(n)\) steps along its own block of \(f(n)\) bits, accepts. Then \(x \in L\) if and only if some \(\ell + 1\) shifts cover \(E_x\), and \(x \notin L\) if and only if some \(\ell + 1\) shifts cover \(\overline{E_x}\).
For a polarity \(b \in \{ 0,1\} \), the matrix language \(M_b\) is the set of \(z\) such that, with \(x\), \(w\), \(r\) the components that the pair decoders read from \(z\) (exactly \(x\), \(w\), \(r\) when \(z = \langle \langle x, w \rangle , r \rangle \)) and \(\ell \) computed from \(|x|\): if \(|r| = \ell \), then for some \(i \le \ell \) the majority verdict of the \(R\) runs along \(r \oplus u_i\) equals \(b\), where \(u_0, \dots , u_{\ell } \in \{ 0,1\} ^{\ell }\) are the consecutive blocks of \(w\) (bits beyond \(|w|\) read as \(0\)). If \(p\) and \(q\) are polynomials with \((\ell + 1)\ell \le p(n)\) and \(\ell \le q(n)\) for all \(n\), then \(L = \exists ^p \forall ^q M_1\) and \(\overline{L} = \exists ^p \forall ^q M_0\).
Finally, if every path of \(N\) halts within \(T(|x|)\) steps, then \(\mathrm{acceptProb}_N(x, T') = \mathrm{acceptProb}_N(x, T(|x|))\) for every \(T' \ge T(|x|)\), so both bounded-error conditions transfer from the clock \(T\) to any pointwise larger clock.
The acceptance probability at clock \(f\) is the probability of the single-trial accepting event, so majority amplification with exponent \(f(n) + 11\) bounds the failure event by \(2^{-(f(n)+11)}\). Since \(\ell {\lt} (f(n) + 11)(\ell + 1)\) the covering lemma gives covering shifts, and since \(\ell + 1 {\lt} 2^{f(n)+11}\) it rules them out in the other case. The existential witness encodes the covering tuple, and the universal variable ranges over encoded seeds. For the last part, the surplus choice bits split the enlarged sample space into equal fibers over the original one.
For every machine \(N\), polynomial \(p \in \mathbb {N}[X]\), and polarity \(b\), take the clock \(f = p\) in Lemma 166. The verdict function \(z \mapsto [z \in M_b]\), with one output bit, is in \(\mathsf{FP}\); consequently \(M_b \in \mathsf{P}\).
No machine is constructed. The verdict is written in Cobham’s algebra: payload scanners decode the triple, the trial count and seed length are \(\mathrm{smash}\) lengths built from \(p\), and each trial is one run of \(N\) along its block of choice bits, simulated inside the algebra. The verdict function then decides \(M_b\) in polynomial time.
\(\mathsf{BPP} \subseteq \Sigma ^p_2 \cap \Pi ^p_2\).
Replace the machine’s time bound by a pointwise dominating polynomial \(P\), which does not change acceptance probabilities once every path has halted. With \(B = (12P + 133)P\), the polynomials \(p = (B + 1)B\) and \(q = B\) bound the witness and seed lengths, so Lemma 166 writes \(L\) and \(\overline{L}\) as \(\exists ^p \forall ^q M_1\) and \(\exists ^p \forall ^q M_0\). By Lemma 167 both matrices are in \(\mathsf{P}\), so \(\forall ^q M_b \in \Pi ^p_1\) and \(L, \overline{L} \in \Sigma ^p_2\); the second gives the \(\Pi ^p_2\) half directly.
\(\mathsf{BPP} \subseteq \mathsf{PH}\).
\(\Sigma ^p_2 \subseteq \mathsf{PH}\).
5.4 Counting classes
\(\mathrm{acceptLeafCount}_N(x, T)\) is the number of accepting leaves of the computation tree of \(N\) on \(x\) truncated at depth \(T\): a halted configuration contributes \(1\) if its output cell \(1\) equals \(1\) and \(0\) otherwise, a configuration that has not halted at depth \(T\) contributes \(0\), and any other configuration contributes the sum over its two successors. So a path that halts at depth \(t {\lt} T\) is one leaf, unlike in \(\mathrm{acceptCount}\). \(\# \mathsf{P}\) is the set of \(f \colon \{ 0,1\} ^* \to \mathbb {N}\) for which some machine \(N\), some \(k\), and some \(T = O(n^k)\) satisfy: every path halts within \(T(|x|)\) steps and \(f(x) = \mathrm{acceptLeafCount}_N(x, T(|x|))\) for every \(x\).
For every machine \(N\), input \(x\), and \(T \in \mathbb {N}\), \(\mathrm{acceptLeafCount}_N(x, T) \le 2^T\) (more generally, the tree rooted at any configuration and truncated at depth \(T\) has at most \(2^T\) accepting leaves), and likewise \(\mathrm{acceptCount}_N(x, T) \le 2^T\). If every length-\(T\) choice sequence leaves \(N\) on \(x\) in a halted configuration after \(T\) steps and \(T \le T'\), then \(\mathrm{acceptLeafCount}_N(x, T') = \mathrm{acceptLeafCount}_N(x, T)\); in particular, if every path halts within \(T(|x|)\) steps for every \(x\) and \(T \le T'\) pointwise, the accepting-leaf counts at \(T'(|x|)\) and \(T(|x|)\) agree for every \(x\), so a \(\# \mathsf{P}\) value does not depend on the choice of a sufficient clock. (No such invariance is claimed for \(\mathrm{acceptCount}\), which counts length-\(T\) choice strings, so a path that halts early is counted once for each unused suffix.) For every \(f \in \# \mathsf{P}\) there are \(k\) and \(T = O(n^k)\) such that \(f(x) \le 2^{T(|x|)}\) for every \(x\).
Induction on the depth of the truncated tree; \(\mathrm{acceptCount}\) counts a subset of the \(2^T\) choice sequences.
\(\mathsf{GapP}\) is the set of \(h \colon \{ 0,1\} ^* \to \mathbb {Z}\) of the form \(h = f - g\) with \(f, g \in \# \mathsf{P}\).
If \(h \in \mathsf{GapP}\) then \(-h \in \mathsf{GapP}\).
Swap the two \(\# \mathsf{P}\) functions.
\(\mathsf{GapP}\) is closed under addition and multiplication, and \(L \in \mathsf{PP}\) if and only if there is \(h \in \mathsf{GapP}\) with \(x \in L \iff h(x) {\gt} 0\) for all \(x\).
\(\mathsf{PP}\) counts fixed-length random strings while \(\# \mathsf{P}\) counts leaves. Pad the machine so that every path halts at exactly the clock, after which the two counts agree, and take \(h(x) = 2\, \mathrm{acceptCount}(x, T) - 2^T\). For the converse, realize the positive and negative parts of \(h\) by one machine with balanced branches.
If \(L \in \mathsf{PP}\) then \(\overline{L} \in \mathsf{PP}\).
Complementing the verdict turns “\({\gt} 1/2\)” into “\(\le 1/2\)”, and ties are the obstacle. With \(h \in \mathsf{GapP}\) integer-valued and \(x \in L \iff h(x) {\gt} 0\), pass to the gap \(1 - 2h\), which is positive exactly when \(h \le 0\).
\(\mathsf{PP}\) is closed under intersection and union.
Approximate the sign function by low-degree rational functions and evaluate them on \(\mathsf{GapP}\) values.
\(\mathsf{PH} \subseteq \mathsf{P}^{\# \mathsf{P}}\).
Needs polynomial-time machines with a function oracle, the Valiant–Vazirani isolation lemma (from pairwise-independent hashing), modular counting, and polynomial interpolation.
5.5 Polynomial-space upper bounds
The two containments below are proved by bespoke enumerating machines. They could instead be routed through the polynomial-space iteration theorem SpaceIter.mem_PSPACE_of_iterate, as Savitch’s theorem and \(\mathsf{IP} \subseteq \mathsf{PSPACE}\) are.
For every machine \(N\), input \(x\) and clock \(T\), \(\mathrm{acceptProb}_N(x, T) {\gt} 1/2 \iff 2^T {\lt} 2 \cdot \mathrm{acceptCount}_N(x, T)\). Hence for every \(L \in \mathsf{PP}\) there are a machine \(N\), some \(m\), and a clock \(f = O(n^m)\) such that every path halts within \(f(|x|)\) steps and \(x \in L \iff 2^{f(|x|)} {\lt} 2 \cdot \mathrm{acceptCount}_N(x, f(|x|))\).
Clear the denominator in \(\mathrm{acceptCount}/2^T {\gt} 1/2\).
\(\mathsf{PP} \subseteq \mathsf{PSPACE}\).
Dominate the clock pointwise by a polynomial \(p\). A deterministic machine evaluates the horizon from \(|x|\) and enumerates the choice sequences up to it on a counter tape that doubles as the choice tape, simulates one path at a time, updates two tallies, and wipes its scratch space between passes; the loop is exponentially long but each pass stays in the same polynomial window. (The simulated machine is prefixed by two steps that ignore their choice bits, which doubles the accepting count, matched by doubling the horizon; a source machine whose start state is its halting state has no accepting path and is handled by a machine that outputs \(0\).)
If \(\mathsf{PSPACE}\) is closed under complement and \(\exists \mathsf{PSPACE} \subseteq \mathsf{PSPACE}\), then \(\Sigma ^p_k \subseteq \mathsf{PSPACE}\) for every \(k\), and hence \(\mathsf{PH} \subseteq \mathsf{PSPACE}\). For every polynomial \(p\) and every \(L' \in \mathsf{PSPACE}\) there are a deterministic machine and a polynomial \(Q\) such that every configuration the machine reaches on \(x\) is within decision space \(Q(|x|)\) and the machine halts on every \(x\) with output \(1\) if \(x \in \exists ^p L'\) and \(0\) otherwise; hence \(\exists \mathsf{PSPACE} \subseteq \mathsf{PSPACE}\). Consequently \(\mathsf{PH} \subseteq \mathsf{PSPACE}\).
Induct on the level, starting from \(\mathsf{P} \subseteq \mathsf{PSPACE}\) and using monotonicity of \(\exists \). Complement is Lemma 203: rerun the machine and flip the verdict with one extra cell. For the existential, the machine enumerates the witnesses of length at most \(p(|x|)\) on one reused work tape, driven by a single counter below \(2^{p(|x|)+1}\), and runs a decider for \(L'\) on each pair; by Lemma 204 this puts \(\exists ^p L'\) in \(\mathsf{PSPACE}\).
\(\mathsf{BPP} \subseteq \mathsf{PSPACE}\).
5.6 Hashing and approximate counting
The results of this section are finite statements about a fixed set \(S \subseteq \{ 0,1\} ^n\) and a uniformly random seed; probabilities are normalized counts over seeds. Only Lemma 184 and Corollary 189 involve a computation model (circuits), and Stockmeyer’s theorem for \(\# \mathsf{P}\) with an \(\mathsf{NP}\) oracle remains planned.
A pairwise-independent family from \(n\)-bit to \(m\)-bit strings with \(s\)-bit seeds is a map \(h \colon \{ 0,1\} ^s \times \{ 0,1\} ^n \to \{ 0,1\} ^m\) such that, over a uniform seed, \(\Pr [h(x) = y] = 2^{-m}\) for all \(x, y\), and \(\Pr [h(x) = y \wedge h(x') = y'] = 2^{-2m}\) for all \(x \neq x'\) and all \(y, y'\). The affine family \(x \mapsto Ax + b\) over \(\mathrm{GF}(2)\), whose seed lists the \(m\) rows \((a_i, b_i)\) of \(n + 1\) bits each, so \(s = m(n+1)\), is one. For \(S \subseteq \{ 0,1\} ^n\), a target \(y \in \{ 0,1\} ^m\) and a seed \(\sigma \), the cell is \(C_\sigma = \{ x \in S : h_\sigma (x) = y\} \); \(\mu \) and \(\mathrm{Var}\) denote the average and the variance of \(|C_\sigma |\) over all \(2^s\) seeds.
For every pairwise-independent family, \(S \subseteq \{ 0,1\} ^n\) and target \(y\): \(\mu = |S|/2^m\); the average number of ordered pairs of distinct members of \(C_\sigma \), which is \(|C_\sigma |(|C_\sigma | - 1)\), is \((|S|^2 - |S|)/2^{2m}\); the average of \(|C_\sigma |^2\) is the sum of these two; and \(\mathrm{Var} = (|S|/2^m)(1 - 2^{-m})\), so \(0 \le \mathrm{Var} \le \mu \). For every \(r {\gt} 0\), \(\Pr [\, \bigl||C_\sigma | - \mu \bigr| \ge r\, ] \le \mathrm{Var}/r^2 \le \mu /r^2\), and if \(\varepsilon {\gt} 0\) and \(\mu {\gt} 0\) then \(\Pr [\, \bigl||C_\sigma | - \mu \bigr| \ge \varepsilon \mu \, ] \le 1/(\varepsilon ^2\mu )\). For occupancy, \(\Pr [C_\sigma \neq \emptyset ] \le \mu \), and if \(\mu {\gt} 0\) then \(\Pr [C_\sigma = \emptyset ] \le 1/\mu \), so \(\Pr [C_\sigma \neq \emptyset ] \ge 1 - 1/\mu \); in particular \(\Pr [C_\sigma \neq \emptyset ] \le 1/8\) when \(\mu \le 1/8\) and \(\Pr [C_\sigma \neq \emptyset ] \ge 7/8\) when \(\mu \ge 8\). Finally, let the amplified occupancy test on \((12k + 1)s\) seed bits return the strict majority of the answers “\(C_\sigma \neq \emptyset \)” for its \(12k + 1\) blocks \(\sigma \). If \(\mu \ge 8\) it returns \(1\) with probability at least \(1 - 2^{-k}\) (so \(0\) with probability at most \(2^{-k}\)), and if \(\mu \le 1/8\) it returns \(1\) with probability at most \(2^{-k}\).
Summing over the members and the ordered pairs of \(S\), uniformity and pairwise independence give the two factorial moments. Chebyshev’s inequality is the finite Markov bound applied to the squared deviation, and \(C_\sigma = \emptyset \) forces a deviation of at least \(\mu \). The occupancy gap \(7/8\) versus \(1/8\) lies outside \([1/3, 2/3]\), so majority amplification over \(12k + 1\) blocks applies.
Let \(N \ge 1\), and let index maps select, among \(N\) primary input wires, the \(m(n + 1)\) coefficients of \(m\) affine forms \(x \mapsto \langle a_i, x \rangle \oplus b_i\) over \(\mathrm{GF}(2)\) and the \(n\) coordinates of \(x\). There is a raw fan-in-two circuit (a gate list whose last gate is the output) with exactly \(m(4n + 4) + 2m + 4\) gates that is well formed over \(N\) inputs and, on every \(N\)-bit input, evaluates to \(1\) exactly when all \(m\) selected forms vanish on the selected \(x\). When the coefficients are the rows of an affine-hash seed \(\sigma \), this is the test \(h_\sigma (x) = 0^m\).
One AND gate per coefficient-coordinate product and a linear-size parity fragment per row compute each form; a threshold fragment detecting a nonzero row, followed by one negated copy gate, gives the all-zero test.
For naturals \(a\) and \(e\): \(e\) approximates \(a\) within factor \(F\) if \(e \le Fa\) and \(a \le Fe\); and \(e\) approximates \(a\) with relative error \(1/q\) if \(q {\gt} 0\) and \((q - 1)a \le qe \le (q + 1)a\), that is, \((1 - 1/q)a \le e \le (1 + 1/q)a\).
Given answers \(\rho _0, \dots , \rho _{n+3} \in \{ 0,1\} \), one per hash width \(j\), the estimate is \(0\) if \(\rho _0 = 0\) and otherwise \(2^{j^*}\), where \(j^*\) is the largest \(j\) with \(\rho _j = 1\); it is always below \(2^{n+4}\). Call the answers accurate for \(a\) if \(\rho _0 = [a {\gt} 0]\), \(\rho _j = 1\) whenever \(8 \cdot 2^j \le a\), and \(\rho _j = 0\) whenever \(8a \le 2^j\). If \(a \le 2^n\) and the answers are accurate for \(a\), the estimate approximates \(a\) within factor \(16\). The hashing estimator for \(S \subseteq \{ 0,1\} ^n\) with amplification \(k\) sets \(\rho _0 = [S \neq \emptyset ]\) and, for \(j \ge 1\), takes \(\rho _j\) to be the amplified occupancy test of Lemma 183 for the affine family to \(j\) bits and target \(0^j\), each width on its own block of the seed. The probability that some answer is not accurate for \(|S|\) is at most \((n + 4)2^{-k}\), so the estimator approximates \(|S|\) within factor \(16\) with probability at least \(1 - (n + 4)2^{-k}\), and at least \(3/4\) when \(k = n + 4\).
At width \(j\) the mean cell size is \(|S|/2^j\), so the widths that must answer \(1\) have mean at least \(8\) and those that must answer \(0\) have mean at most \(1/8\); the amplified occupancy bounds and a union bound over the \(n + 4\) widths give the probability. The factor-\(16\) bound is arithmetic on the largest positive width.
The \(c\)-fold Cartesian power \(S^c \subseteq \{ 0,1\} ^{cn}\) of \(S \subseteq \{ 0,1\} ^n\), encoded row-major, consists of the strings all of whose \(n\)-bit blocks lie in \(S\), and \(|S^c| = |S|^c\). If \(c \ge 1\), \(q \ge 1\), \(F^2 q^c \le (q + 1)^c\), and \(e\) approximates \(a^c\) within factor \(F\), then \(\lfloor (Fe)^{1/c} \rfloor \) approximates \(a\) with relative error \(1/q\). For \(F = 16\) and \(c = 8q\) the separation condition holds for every \(q \ge 1\), so a factor-\(16\) estimate \(e\) of \(|S^{8q}|\) yields the relative estimate \(\lfloor (16e)^{1/(8q)} \rfloor \) of \(|S|\).
Multiplying by \(F\) before the floor root selects the upper endpoint of the interval \([e/F, Fe]\) containing \(a^c\), and the separation condition makes the \(c\)-th root of that interval shorter than the relative-error window.
Let \(S \subseteq \{ 0,1\} ^n\), let \(q \ge 1\) be an integer, and let \(t \ge 0\). The relative hashing estimator runs the constant-factor hashing estimator of Lemma 186 on \(S^{8q}\) with amplification \(k = 8qn + 2 + t\) and returns \(\lfloor (16w)^{1/(8q)} \rfloor \) for its output \(w\). With probability at least \(1 - 2^{-t}\) over the seed, its output \(e\) satisfies \((q - 1)|S| \le qe \le (q + 1)|S|\); for \(t = 2\) this probability is at least \(3/4\). Its output is always below \(2^{n+1}\). By construction (this is a property of the definition, not a separate theorem), the estimator reads \(S\) only through whether \(S^{8q}\) is nonempty and whether zero cells \(\{ z \in S^{8q} : h(z) = 0^j\} \) of affine hashes \(h\) are nonempty.
Stockmeyer’s scheme. The constant-factor estimator on \(S^{8q}\), of width \(8qn\), fails with probability at most \((8qn + 4)2^{-(8qn + 2 + t)} \le 2^{-t}\), and on success the Cartesian-power lemma converts its factor-\(16\) estimate of \(|S|^{8q}\) into a relative-error-\(1/q\) estimate of \(|S|\).
Let \(C\) be a fan-in-two circuit with \(s + a\) inputs, \(a \ge 1\), and \(M \ge 1\) outputs, whose first \(s\) inputs are a random seed, and let a decidable predicate say which outputs are correct for which inputs \(u \in \{ 0,1\} ^a\). If for every \(u\) the seeds \(\sigma \) on which \(C(\sigma u)\) is incorrect for \(u\) have probability at most \(2^{-(a+1)}\), then one seed is correct for every \(u\), and hardwiring it gives a circuit on \(a\) inputs with the same internal gate count and the same size that is correct for every \(u\).
Now fix \(q \ge 1\), \(t\), and sets \(S_u \subseteq \{ 0,1\} ^n\) for \(u \in \{ 0,1\} ^a\), and say \(C\) implements the relative estimator if, for every seed \(\sigma \) and every \(u\), the output of \(C(\sigma u)\) read as a little-endian unsigned integer equals the output of the estimator of Theorem 188 on \(S_u\) with seed \(\sigma \). Then \(C\) fails to output a relative-error-\(1/q\) approximation of \(|S_u|\) exactly on the estimator’s failure seeds, hence with probability at most \(2^{-t}\) for every \(u\); for \(t = a + 1\), hardwiring a seed gives a circuit of the same size that is accurate on every \(u\). The same holds for a fixed-round adaptive oracle program of fan-in-two circuits (AdaptiveOracleProgram): inlining circuits that answer every query of the right width as the oracle does preserves implementing the estimator, and if the program implements it with \(t = a + 1\) relative to every oracle deciding a language \(A \in \mathsf{P/poly}\), then for some polynomial-size circuit family deciding \(A\), inlining that family and hardwiring a seed gives an ordinary circuit, of the same size as the inlined program, that is accurate on every \(u\).
A union bound over the \(2^a\) inputs leaves a seed that is good for all of them, and fixing an input prefix keeps the gates. For the estimator the bad seeds of \(C\) are exactly the failure seeds, whose probability is bounded by Theorem 188; for oracle programs, first inline the circuit oracle, which preserves every output.
For every \(f \in \# \mathsf{P}\) and polynomial \(q\), a probabilistic polynomial-time machine with an \(\mathsf{NP}\) oracle outputs, with probability at least \(2/3\), a value \(e\) with \((1 - 1/q(|x|)) f(x) \le e \le (1 + 1/q(|x|)) f(x)\).
Pad the machine so that every path halts exactly at the clock, so that its accepting leaves correspond to its accepting choice sequences, and apply Theorem 188 to that set, answering each cell-occupancy question with one \(\mathsf{NP}\) query. Probabilistic oracle machines are not defined yet; the circuit-level form of the seed and oracle bookkeeping is Corollary 189.