他の計算量クラスとの関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/14 02:46 UTC 版)
「BPP (計算複雑性理論)」の記事における「他の計算量クラスとの関係」の解説
BPPは、補問題について閉じていることが知られている。つまり、BPP=co-BPPである。このクラスは特に NP との位置が不定のクラスである。P ⊆ {\displaystyle \subseteq } BPP ⊆ {\displaystyle \subseteq } PH は証明されている。しかし NP ⊆ {\displaystyle \subseteq } BPP なのか、BPP ⊆ {\displaystyle \subseteq } NP なのか、あるいは BPP = NP なのかは不明である。 なおこのクラスとよく似た誤り確率が高々1/2 のクラス（クラスPP）は NP を含むことが証明されている。 確率的チューリングマシンを少し拡張すると、量子チューリングマシンができるのと同じように、BPPの量子コンピュータに対応する計算量のクラスとしてBQPが存在する。
※この「他の計算量クラスとの関係」の解説は、「BPP (計算複雑性理論)」の解説の一部です。
「他の計算量クラスとの関係」を含む「BPP (計算複雑性理論)」の記事については、「BPP (計算複雑性理論)」の概要を参照ください。
他の計算量クラスとの関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 09:54 UTC 版)
このクラスは量子コンピュータのために定義されたもので、古典コンピュータ（または、ランダムな挙動を許したチューリングマシン）に自然な対応をするクラスはBPPである。 BQPはPとBPPを含み、PPとPSPACEに含まれる。まとめると以下のような関係がある。 P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE {\displaystyle {\mbox{P}}\subseteq {\mbox{BPP}}\subseteq {\mbox{BQP}}\subseteq {\mbox{PP}}\subseteq {\mbox{PSPACE}}} BQPとNPの関係については、2010年代ころより、NPを含むPHにBQPが含まれない、ということを示唆する結果がいくつか示されてきている。 表 話 編 歴 主な複雑性クラス(一覧)実用的な時間で解けるクラスDLOGTIME AC0 ACC0 TC0 L SL RL NL NC SC CC PP完全 ZPP RP BPP BQP APX 実用的な時間で解けないと疑われているクラスUP NPNP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P#P完全 IP PSPACE 実用的な時間では解けないクラスEXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL クラス階層多項式階層 指数階層 グジェゴルチク階層 算術的階層 ブーリアン階層 クラスの族DTIME NTIME DSPACE NSPACE PCP 対話型証明系
※この「他の計算量クラスとの関係」の解説は、「BQP」の解説の一部です。
「他の計算量クラスとの関係」を含む「BQP」の記事については、「BQP」の概要を参照ください。
- 他の計算量クラスとの関係のページへのリンク
