Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR01-068 | 12th February 2002 00:00

P(APP) = P(prBPP) Revision of: TR01-068

RSS-Feed




Revision #1
Authors: Philippe Moser
Accepted on: 12th February 2002 00:00
Downloads: 3317
Keywords: 


Abstract:

We show that for deterministic polynomial time computations, 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
in $\mathbf{prBPP}$, and that preserves completeness, i.e. maps complete functions to complete promise problems.
Next, we construct
a mapping from
$\mathbf{prBPP}$ into $\mathbf{APP}$, that maps every promise problem to a function
in $\mathbf{APP}$, and which preserves completeness.
Then, we prove that $\mathbf{P^{\mathbf{APP}}} = \mathbf{P^{\mathbf{prBPP}}}$.
Finally, we use our results to simplify proofs of important results on $\mathbf{APP}$, such as
the $\mathbf{APP}$-completeness of the function $f_{\mathrm{CAPP}}$,
which approximates the acceptance
probability of a Boolean circuit, the error probability reduction Theorem
for $\mathbf{APP}$ functions, and the conditional derandomization result
$\mathbf{APP} = \mathbf{AP} \mbox{ iff } \mathbf{prBPP}$ is easy.


Paper:

TR01-068 | 19th September 2001 00:00

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





TR01-068
Authors: Philippe Moser
Publication: 5th October 2001 18:36
Downloads: 3499
Keywords: 


Abstract:

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
in $\mathbf{prBPP}$, and that maps complete functions to complete promise problems.
Then we show an analogue result in the opposite direction, by constructing a mapping from
$\mathbf{prBPP}$ into $\mathbf{APP}$, that maps every promise problem to a function
in $\mathbf{APP}$, and mapping complete promise problems to complete functions.
Second we prove that $\mathbf{P^{\mathbf{APP}}} = \mathbf{P^{\mathbf{prBPP}}}$.
Finally we use our results to simplify proofs of important results on $\mathbf{APP}$, such as
the $\mathbf{APP}$-completeness of the function $f_{\mathrm{CAPP}}$ that approximates the acceptance
probability of a Boolean circuit, or the possibility (similarily
to the case of $\mathbf{BPP}$) to reduce the
error probability for $\mathbf{APP}$ functions, or the conditionnal derandomization result
$\mathbf{APP} = \mathbf{AP} \mbox{ iff } \mathbf{prBPP}$ is easy.



ISSN 1433-8092 | Imprint