AWPP (complexitat)
En complexitat computacional, AWPP (Almost Wide Probabilistic Polynomial time) és la classe de complexitat que conté els problemes que es poden solucionar amb una màquina NP tal que per algunes funcions f computables en temps polinòmic:[1][2]
- si la resposta és «no», llavors la diferència entre el nombre de camins que accepten i que rebutgen és no negatiu i com a mínim
- si la resposta és "si", llavors la diferència està entre i
Relació amb d'altres classes
[modifica]La classe AWPP conté a BQP i és la millor fita superior coneguda d'aquesta classe.
AWPP també conté les classes WAPP, LWPP i WPP.[3][4]
AWPP està continguda dins la classe APP.[5]
Referències
[modifica]- ↑ «Gap-definable counting classes». Journal of Computer and System Sciences. [Consulta: 8 gener 2019].
- ↑ «Complexity Zoo:A - Complexity Zoo». Arxivat de l'original el 2018-12-01. [Consulta: 8 gener 2019].
- ↑ Fortnow, Lance; Rogers, John D. «Complexity limitations on quantum computation». arXiv:cs/9811023, 12-11-1998.
- ↑ E. Böhler, C. Glaßer, and D. Meister «Error-bounded probabilistic computations between MA and AM». Mathematical foundations of computer science, 2003, pàg. 249-258. Arxivat de l'original el 2007-06-10 [Consulta: 8 gener 2019]. Arxivat 2007-06-10 a Wayback Machine.
- ↑ «PP-lowness and a simple definition of AWPP». Theory Comput. Syst., 2003. [Consulta: 8 gener 2019].
| Considerades tractables | |
|---|---|
| Suposadament intractables | UP · NP · NP-complet · NP-hard · co-NP · co-NP-complet · AM · QMA · PH · ⊕P · PP · ♯P · ♯P-complet · IP · PSPACE · PSPACE-complet |
| Considerades intractables | |
| Jerarquia de classes | |
| Families de classes | |
