AWPP

理論計算機科学において、ほぼ広域確率多項式時間( AWPP ) は、GapP関数によって定義されるPPに含まれる計算量クラスです。このクラスは、量子コンピューティングのコンテキストでよく登場します。

AWPP には、量子コンピュータが多項式時間で解ける決定問題（すべてのインスタンスでエラー確率が最大 1/3）を含む複雑性クラスBQP（限界誤差量子多項式時間）が含まれます。実際、これは BQP の上限となる最小の古典的複雑性クラスです。さらに、これは APP クラスに含まれています。

• ランス・フォートナウ、ジョン・D・ロジャース (1999)。「量子計算における複雑性の限界」。コンピュータとシステム科学ジャーナル。59 ( 2): 240–252。arXiv : cs/9811023。doi : 10.1006/JCSS.1999.1651。さまざまな複雑性クラス間の接続に関する情報を提供します。AWPP における BPQ の証明。
• Fenner, Stephen A. (2003). 「PP の低さと AWPP の簡単な定義」.コンピューティングシステムの理論. 36 (2): 199–212. doi :10.1007/s00224-002-1089-8. MR  1950277. ECCC  TR02-036.AWPP の定義と APP および PP への接続。
• Fenner, Stephen A.; Fortnow, Lance J.; Kurtz, Stuart A. (1994). 「ギャップ定義可能なカウントクラス」. Journal of Computer and System Sciences . 48 (1): 116–148. doi : 10.1016/S0022-0000(05)80024-8 . MR  1259653.定義が含まれています。
• Fenner, Stephen; Fortnow, Lance; Kurtz, Stuart A.; Li, Lide (2003). 「オラクルビルダーのツールキット」.情報と計算. 182 (2): 95–136. doi :10.1016/S0890-5401(03)00018-X. MR  1971487.定義が含まれています。

• 「Complexity Zoo」は、Wayback Machineで 2018-12-01 にアーカイブされています。AWPP を含む複雑性クラスのリストと、他のクラスとの関係が含まれています。