__
Revision #1 to TR01-068 | 12th February 2002 00:00
__
#### P(APP) = P(prBPP) Revision of: TR01-068

**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.

__
TR01-068 | 19th September 2001 00:00
__

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

**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.