In
theoretical computer science
Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation.
It is difficult to circumscribe the theoretical areas precisely. The Associati ...
, almost wide probabilistic polynomial-time (AWPP) is a
complexity class
In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...
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
A quantum computer is a computer that exploits quantum mechanical phenomena. On small scales, physical matter exhibits properties of wave-particle duality, both particles and waves, and quantum computing takes advantage of this behavior using s ...
.
AWPP contains the complexity class
BQP (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 on a set of input values. An example of a decision problem is deciding whether a given natura ...
s solvable by a quantum computer in
polynomial time
In theoretical 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 p ...
, 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. Proof of BPQ in AWPP.
* Definition of AWPP and connection to APP and PP.
* Contains definitions.
* 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