To print higher-resolution math symbols, click the
Hi-Res Fonts for Printing button on the jsMath control panel.

jsMath
Loading jsMath...
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