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 si la resposta és "si", llavors la diferència està entre i
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.
Referències
Categoria:Complexitat computacional Categoria:Classes de complexitat