Usually called AP in the literature. I've renamed it AxP to distinguish it from the "other" AP.
The class of real-valued functions from {0,1}n to [0,1] that can be approximated within any ε>0 by a deterministic Turing machine in time polynomial in n and 1/ε.
Defined by [KRC00], who also showed that the set of AxP machines is in RE.
An alternating Turing machine is a nondeterministic machine with two kinds of states, AND states and OR states. It accepts if and only if the tree of all computation paths, considered as an AND-OR tree, evaluates to 1. (Here 'Accept' corresponds to 1 and 'Reject' to 0.)
Then AP is the class of decision problems solvable in polynomial time by an alternating Turing machine.
The abbreviation AP is also used for Approximable in Polynomial Time, see AxP.
Usually called APP. I've renamed it AxPP to distinguish it from the "other" APP.
The class of real-valued functions from {0,1}n to [0,1] that can be approximated within any ε>0 by a probabilistic Turing machine in time polynomial in n and 1/ε.
Defined by [KRC00], who also show the following:
AxPP is recursively enumerable [Jeř07].