2008/10/06 by Cristopher Moore, Alexander Russell, Moore, Cristopher +1
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Methods in Verification #Machine Learning and Algorithms #Polynomial and algebraic computation #cs.CC
paper · pdf · doi:10.48550/arxiv.0810.1018
arxiv created 2008/10/06 · openalex publication_date 2008/10/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in ¶# P relies on the fact that, under mild technical conditions on the complexity class C, we have ∃ C ⊂ BP ⋅ ⊕ C. More concretely, there is a randomized reduction which transforms nonempty sets and the empty set, respectively, into sets of odd or even size. The customary method is to invoke Valiant's and Vazirani's randomized reduction from NP to UP, followed by amplification of the resulting success probability from 1/\poly(n) to a constant by combining the parities of \poly(n) trials. Here we give a direct algebraic reduction which achieves constant success probability without the need for amplification. Our reduction is very simple, and its analysis relies on well-known properties of the Legendre symbol in finite fields.