Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > REAL FUNCTIONS:
Reports tagged with real functions:
TR02-006 | 8th November 2001
Philippe Moser

#### Random nondeterministic real functions and Arthur Merlin games

Revisions: 1

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

ISSN 1433-8092 | Imprint