Moser, Philippe
(2002)
P(APP) = P(prBPP).
Technical Report.
Electronic Colloquium on Computational Complexity.
Abstract
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.
| Item Type: |
Monograph
(Technical Report)
|
| Keywords: |
computationnal complexity; Randomness; |
| Academic Unit: |
Faculty of Science and Engineering > Computer Science |
| Item ID: |
10308 |
| Identification Number: |
Revision #1 to TR01-068 |
| Depositing User: |
Philippe Moser
|
| Date Deposited: |
11 Dec 2018 15:58 |
| Publisher: |
Electronic Colloquium on Computational Complexity |
| URI: |
|
| Use Licence: |
This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available
here |
Repository Staff Only(login required)
 |
Item control page |
Downloads per month over past year
Origin of downloads
Altmetric
Altmetric