In
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
, almost wide probabilistic polynomial-time (AWPP) is a
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms of ...
contained in
PP defined via
GapP
GapP is a counting complexity class, consisting of all of the functions ''f'' such that there exists a polynomial-time non-deterministic Turing machine ''M'' where, for any input ''x'', ''f(x)'' is equal to the number of accepting paths of ''M'' ...
functions. The class often arises in the context of
quantum computing
Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Though ...
.
AWPP contains the complexity class
BQP
In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances.Michael Nielsen and Isa ...
(bounded-error quantum polynomial time), which contains the
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
s solvable by a quantum computer in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
, with an error probability of at most 1/3 for all instances. In fact, it is the smallest classical complexity class that upper bounds BQP. Furthermore, it is contained in the
APP class.
References
General
* Provides information on the connection between various complexity classes.
* Definition of AWPP and connection to APP and PP.
* Proof of BPQ in AWPP.
* "Gap-definable counting classes" by S. Fenner, L. Fortnow, and S. Kurtz from the ''Journal of Computer and System Sciences''. Pages 116–148, 1994, issue 48. Contains definitions.
* "An oracle builder's toolkit" by S. Fenner, L. Fortnow, S. Kurtz, and L. Li. in 8th IEEE Structure in Complexity Theory Conference Proceedings. Pages 120–131, 1993. Contains definitions.
External links
"Complexity Zoo": Contains a list of complexity classes, including AWPP, and their relation to other classes.
Probabilistic complexity classes
Quantum complexity theory
{{comp-sci-theory-stub