Abstract:
We 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}}$.

Abstract:
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}}$.