Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TODA'S THEOREM:
Reports tagged with Toda's theorem:
TR08-093 | 1st October 2008
Cristopher Moore, Alexander Russell

#### A simple constant-probability RP reduction from NP to Parity P

The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $\P^\numP$ relies on the fact that, under mild technical conditions on the complexity class $\mathcal{C}$, we have $\exists \,\mathcal{C} \subset \BP \cdot \oplus \,\mathcal{C}$. More concretely, there is a randomized reduction which transforms nonempty sets and the ... more >>>

ISSN 1433-8092 | Imprint