Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMPUTATIONNAL COMPLEXITY:
Reports tagged with computationnal complexity:
TR01-068 | 19th September 2001
Philippe Moser

Relative to P, APP and promise-BPP are the same

Revisions: 1

We show that for determinictic polynomial time computation, oracle access to
$\mathbf{APP}$, the class of real functions
approximable by probabilistic Turing machines, is the same as having oracle access to
promise-$\mathbf{BPP}$. First
we construct a mapping that maps every function in $\mathbf{APP}$ to a promise problem
more >>>




ISSN 1433-8092 | Imprint