ECCC-Report TR02-006https://eccc.weizmann.ac.il/report/2002/006Comments and Revisions published for TR02-006en-usThu, 07 Feb 2002 00:00:00 +0200
Revision 1
| Random nondeterministic real functions and Arthur Merlin games Revision of: TR02-006 |
Philippe Moser
https://eccc.weizmann.ac.il/report/2002/006#revision1We construct a nondeterministic version of \textbf{APP}, denoted
\textbf{NAPP}, which is the set of all real valued functions
$f: \{ 0,1 \}^{*} \rightarrow [0,1]$, that are approximable within 1/$k$,
by a probabilistic nondeterministic transducer, in time poly($1^{k},n$).
We show that the subset of all Boolean functions in $\mbf{NAPP}$ 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.
$\mbf{P}^{\mbf{NAPP}} = \mbf{P}^{\mbf{prAM}}$.
Thu, 07 Feb 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/2002/006#revision1
Paper TR02-006
| Random nondeterministic real functions and Arthur Merlin games |
Philippe Moser
https://eccc.weizmann.ac.il/report/2002/006 We construct a nondeterministic analogue to \textbf{APP}, denoted
\textbf{NAPP}; which is the set of all real valued functions
$f: \{ 0,1 \}^{*} \rightarrow [0,1]$, that are approximable within 1/$k$,
by a probabilistic nondeterministic transducer, in time poly($n,1^{k}$).
We show that the subset of all Boolean functions in $\mbf{NAPP}$ 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},
mapping complete problems to complete problems.
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.
$\mbf{P}^{\mbf{NAPP}} = \mbf{P}^{\mbf{prAM}}$.
Wed, 09 Jan 2002 21:27:00 +0200https://eccc.weizmann.ac.il/report/2002/006