Class Description

AxP: Approximable in Polynomial Time

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.

Linked From

AP: Alternating P

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.

AP = PSPACE [CKS81].

The abbreviation AP is also used for Approximable in Polynomial Time, see AxP.

More about...


AxPP: Approximable in Probabilistic Polynomial Time

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

More about...