AWPP_(complexity)

AWPP

AWPP

Add article description

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

    This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.
    Share this article:

    This article uses material from the Wikipedia article AWPP_(complexity), and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.