Moser, Philippe
(2002)
Random nondeterministic real functions and Arthur Merlin games.
Technical Report.
Electronic Colloquium on Computational Complexity.
Abstract
We construct a nondeterministic version of \textbf{APP}, denoted
\textbf{NAPP}, which is the set of all real valued functions
f:01[01] , that are approximable within 1/k,
by a probabilistic nondeterministic transducer, in time poly(1kn ).
We show that the subset of all Boolean functions in \mbfNAPP is exactly
\textbf{AM}.
We exhibit a natural complete problem for \textbf{NAPP}, namely computing
the acceptance probability of a nondeterministic Boolean circuit.
Then we prove that similarly to \textbf{AM}, the error probability
for \textbf{NAPP} functions can be reduced exponentially.
We also give a co-nondeterministic version, denoted \textbf{coNAPP}, and prove
that all results for \textbf{NAPP} also hold for \textbf{coNAPP}.
Then we construct two mappings between \tbf{NAPP} and promise-\tbf{AM},
which preserve completeness.
Finally we show that in the world of deterministic computation, oracle access to
\textbf{AM} is the same as oracle access to \textbf{NAPP}, i.e.
\mbfP\mbfNAPP=\mbfP\mbfprAM.
| Item Type: |
Monograph
(Technical Report)
|
| Keywords: |
Arthur Merlin games; Randomness; real functions; |
| Academic Unit: |
Faculty of Science and Engineering > Computer Science |
| Item ID: |
10309 |
| Identification Number: |
Revision #1 to TR02-006 |
| Depositing User: |
Philippe Moser
|
| Date Deposited: |
11 Dec 2018 16:35 |
| 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