# Random nondeterministic real functions and Arthur Merlin games

Moser, Philippe (2002) Random nondeterministic real functions and Arthur Merlin games. Technical Report. Electronic Colloquium on Computational Complexity.

 Preview
Official URL: https://eccc.weizmann.ac.il/report/2002/006/

more...

## 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) Arthur Merlin games; Randomness; real functions; Faculty of Science and Engineering > Computer Science 10309 Revision #1 to TR02-006 Philippe Moser 11 Dec 2018 16:35 Electronic Colloquium on Computational Complexity