В теоретической информатике почти широковероятностное полиномиальное время ( AWPP ) — это класс сложности, содержащийся в PP , определенный через функции GapP . Этот класс часто возникает в контексте квантовых вычислений .
AWPP содержит класс сложности BQP (квантовое полиномиальное время с ограниченной ошибкой), который содержит задачи решения , решаемые квантовым компьютером за полиномиальное время , с вероятностью ошибки не более 1/3 для всех случаев. Фактически, это наименьший классический класс сложности, который ограничивает BQP сверху. Более того, он содержится в классе APP .