Official URL: https://eccc.weizmann.ac.il/report/2001/068/

We show that for deterministic polynomial time computations, oracle access to APP, the class of real functions approximable by probabilistic Turing machines, is the same as having oracle access to promise-BPP. First, we construct a mapping that maps every function in APP to a promise problem in prBPP, and that preserves completeness, i.e. maps complete functions to complete promise problems. Next, we construct a mapping from prBPP into APP, that maps every promise problem to a function in APP, and which preserves completeness. Then, we prove that PAPP=PprBPP. Finally, we use our results to simplify proofs of important results on APP, such as the APP-completeness of the function fCAPP, which approximates the acceptance probability of a Boolean circuit, the error probability reduction Theorem for APP functions, and the conditional derandomization result APP=AP iff prBPP is easy.