Philippe Moser

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 ...
more >>>