Loading article…
計算複雑性理論では、言語 B (または計算複雑性クラス B ) は、 A B = Aの場合、（ A の何らかの合理的な相対化バージョンを含む）計算複雑性クラスAに対して低いと言われます。つまり、Bのオラクルを持つAはAに等しいということです。[1] このようなステートメントは、Aの問題を解決する抽象マシンは、単位コストでBの問題を解決できる能力が与えられても、追加のパワーを獲得しないことを意味します。特に、これは、B がAに対して低い場合、B がAに含まれていることを意味します。非公式には、低いとは、 Bの問題が、Aの問題を解決できるマシンによって解決できるだけでなく、「解決が容易」であることを意味します。Aマシンは、リソースの限界を超えることなく、 Bへの多くのオラクルクエリをシミュレートできます。
あるクラスが別のクラスに対して低レベルであると判定する結果と関係は、しばしば低レベル結果と呼ばれます。複雑性クラスAに対して低レベルの言語の集合は、Low(A)と表されます。
自分にとって低いクラス
いくつかの自然な複雑性クラスは、それ自体が低いことが知られています。そのようなクラスは、自己低と呼ばれることがあります。[2] スコット・アーロンソンは、そのようなクラスを物理的複雑性クラスと呼んでいます。[3]自己低であることは、補集合に関して閉じていることよりも強い条件であることに注意してください。非公式には、クラスがそれ自体に対して低いということは、問題が複雑性クラスの能力を超えることなく、クラス内の他の問題を単位コストのサブルーチンとして使用できることを意味します。
以下のクラスは自己低レベルであることが知られている: [3]
- 多項式時間アルゴリズムは合成に対して閉じているため、 P は自己低い (つまり、P P = P) です。つまり、多項式時間アルゴリズムは、多項式の実行時間を維持しながら、他の多項式時間アルゴリズムに対して多項式の数のクエリを実行できます。
- PSPACE (制限されたオラクル アクセス メカニズムを使用) も自己低であり、これはまったく同じ議論によって確立できます。
- L は、ログ スペース Oracle クエリをログ スペースでシミュレートし、各クエリに同じスペースを再利用できるため、自己低くなります。
- NCも同じ理由で自己低くなります。
- ZPPもそれ自体が低く、同じ議論がBPPにもほぼ当てはまりますが、エラーを考慮する必要があり、 BPP がそれ自体が低いことを示すのが少し難しくなります。
- 同様に、BPPの議論はBQPにもほぼ当てはまりますが、量子クエリがコヒーレント重ね合わせで実行できることをさらに示す必要があります。[4]
- パリティP（）とBPPはどちらもそれ自体が低い。これらは戸田の定理を示す上で重要であった。[5]
- NP∩coNPはそれ自体が低い。[1]
自身に対して低いクラスはすべて、そのブール結果を否定するほど強力であれば、補集合に対して閉じています。これは、 NP がNP = co-NPでない限り、自身に対して低くないことを意味します。これは、多項式階層が最初のレベルに縮小することを意味するため、ありそうにないと考えられますが、階層は無限であると広く信じられています。このステートメントの逆は真ではありません。クラスが補集合に対して閉じている場合、クラスが自身に対して低いことを意味しません。そのようなクラスの例はEXPで、補集合に対して閉じていますが、自身に対して低くはありません。
他の複雑度クラスでは低いクラス
階級の低さに関するより複雑で有名な結果には、次のようなものがあります。
- BQPはPPに対して低い[6]言い換えれば、ポリタイムランダム化アルゴリズムの無制限の反復の多数決を取ることをベースにしたプログラムは、量子コンピュータが効率的に解決できるすべての問題を簡単に解決できる。
- グラフ同型性問題はパリティP（）では低い。 [7]これは、 NPマシンの受け入れパスが偶数か奇数かを判断できれば、グラフ同型性を簡単に解決できることを意味します。実際、後にZPP NPではグラフ同型性が低いことが示されました。[8]
- 増幅されたPPはPPに対して低い。[9]
- NP∩coNPはNPの低言語集合に等しい、つまりLow(NP) = NP∩coNPである。[1]
- AM∩coAMはZPPNPに対して低い。 [ 1]
アプリケーション
低さは、相対化の議論において特に価値があり、特定のオラクル マシンが無料で利用できる「相対化された宇宙」ではクラスのパワーが変わらないことを証明するために使用できます。これにより、通常と同じ方法で推論できます。たとえば、BQPの相対化された宇宙では、PP は依然として和集合と積集合の下で閉じています。また、低さの結果によってマシンのパワーが同じままになるかどうかが決まることから、オラクルを使用してマシンのパワーを拡大しようとする場合にも役立ちます。
参照
参考文献
- ^ abcd Köbler, Johannes; Torán, Jacobo (2015). 「Lowness の結果: 次世代」Bulletin of the EATCS . 117 .
- ^ Rothe, J. (2006). 複雑性理論と暗号学: 暗号複雑性入門. 理論計算機科学テキスト. EATCS シリーズ. Springer Berlin Heidelberg. ISBN 978-3-540-28520-5. 2017年5月15日閲覧。
- ^ ab “Lens of Computation on the Sciences”。2014年11月25日。2021年5月6日時点のオリジナルよりアーカイブ。 2021年10月17日閲覧。
- ^ Bernstein and Vazirani、「量子複雑性理論」、SIAM Journal on Computing、26(5):1411-1473、1997年。[1] 2011年5月25日にWayback Machineにアーカイブ
- ^ 「アーカイブコピー」（PDF）。2021年5月6日時点のオリジナルよりアーカイブ（PDF） 。 2021年10月17日閲覧。
{{cite web}}: CS1 maint: アーカイブされたコピーをタイトルとして (リンク) - ^ L. Fortnow と JD Rogers。量子計算における複雑性の限界。IEEE Complexity '98 の Proceedings、p.202-209。1998 年。arXiv :cs.CC/9811023。
- ^ V. Arvind と P. Kurur。グラフ同型性は SPP にあります。ECCC TR02-037。2002 年。
- ^ Vikraman Arvind と Johannes Köbler。ZPP(NP) のグラフ同型性は低い、およびその他の低さの結果。第 17 回コンピュータサイエンスの理論的側面に関する年次シンポジウムの議事録、ISBN 3-540-67141-2、p.431-442。2000 年。
- ^ L. Li. 計数関数について。シカゴ大学博士論文。1993年。