AWPP explained

In theoretical computer science, almost wide probabilistic polynomial-time (AWPP) is a complexity class contained in PP defined via GapP functions. The class often arises in the context of quantum computing.

AWPP contains the complexity class BQP (bounded-error quantum polynomial time), which contains the decision problems solvable by a quantum computer in polynomial time, 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

• Fortnow . Lance . Lance Fortnow . Rogers . John D. . cs/9811023 . 10.1006/JCSS.1999.1651 . 2 . Journal of Computer and System Sciences . 240–252 . Complexity Limitations on Quantum Computation . 59 . 1999. Provides information on the connection between various complexity classes. Proof of BPQ in AWPP.
• Fenner . Stephen A. . 10.1007/s00224-002-1089-8 . . 2 . Theory of Computing Systems . 1950277 . 199–212 . PP-lowness and a simple definition of AWPP . 36 . 2003. Definition of AWPP and connection to APP and PP.
• Fenner . Stephen A. . Fortnow . Lance J. . Kurtz . Stuart A. . 10.1016/S0022-0000(05)80024-8 . 1 . Journal of Computer and System Sciences . 1259653 . 116–148 . Gap-definable counting classes . 48 . 1994. free . Contains definitions.
• Fenner . Stephen . Fortnow . Lance . Kurtz . Stuart A. . Li . Lide . 10.1016/S0890-5401(03)00018-X . 2 . Information and Computation . 1971487 . 95–136 . An oracle builder's toolkit . 182 . 2003. Contains definitions.

External links

• "Complexity Zoo" : Contains a list of complexity classes, including AWPP, and their relation to other classes.