Computer Science – Computational Complexity
Scientific paper
2008-10-06
Computer Science
Computational Complexity
Scientific paper
The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $\P^{# P}$ relies on the fact that, under mild technical conditions on the complexity class $C$, we have $\exists C \subset BP \cdot \oplus 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.
Moore Cristopher
Russell Alexander
No associations
LandOfFree
A simple constant-probability RP reduction from NP to Parity P does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A simple constant-probability RP reduction from NP to Parity P, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A simple constant-probability RP reduction from NP to Parity P will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-206271