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:

• 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 $2^{-poly(n)}f(x)$
• si la resposta és "si", llavors la diferència està entre $(1-2^{-poly(n)})f(x)$ i $f(x)$

Relació amb d'altres classes

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.

AWPP està continguda dins la classe APP.