ギャップ定理

数学におけるその他のギャップ定理については、「ギャップ定理 (曖昧さ回避)」も参照してください。

計算複雑性理論において、ギャップ定理（ボロディン・トラクテンブロートギャップ定理とも呼ばれる）は、計算可能関数の計算複雑性に関する主要な定理である。^[1]

これは本質的に、複雑性クラスの階層構造には任意に大きな計算可能なギャップが存在することを述べている。計算資源の増加を表す任意の計算可能関数について、拡張された資源境界内で計算可能な関数の集合が、元の境界内で計算可能な関数の集合と同じになるような資源境界を見つけることができる。

この定理はボリス・トラクテンブロット^[2]とアラン・ボロディン^{[3] [4]}によって独立に証明された。トラクテンブロットの導出はボロディンより数年前に行われたが、ボロディンの研究が出版されるまで 西洋 では知られておらず、認識もされていなかった。

声明

入門例として、ある特定のチューリングマシンモデルの計算時間計算量について考えてみましょう。 集合とは、入力サイズ が与えられた場合に、それを で計算する関数の実装が存在するような計算可能関数全体の集合です。 ${\displaystyle \operatorname {時間} (n^{2})}$ ${\displaystyle \leq n^{2}}$ ${\displaystyle n}$

一般に、任意の全計算可能関数は何らかの時間計算量クラスを定義し、 がよりもはるかに大きい場合、すべての に対してはよりも大きくなるはずです。ギャップ定理は、必ずしもそうではないことを示しています。実際、すべての に対して となる任意の全計算可能関数 に対して、となる全計算可能関数 が存在します。直感的には、計算時間を増やしても、より多くの関数を計算できるわけではないかもしれません。 ${\displaystyle t}$ ${\displaystyle \operatorname {時間} (t(n))}$ ${\displaystyle t'(n)}$ ${\displaystyle t(n)}$ ${\displaystyle n}$ ${\displaystyle \operatorname {TIME} (t'(n))}$ ${\displaystyle \operatorname {時間} (t(n))}$ ${\displaystyle g}$ ${\displaystyle g(n)>n}$ ${\displaystyle n}$ ${\displaystyle t}$ ${\displaystyle \operatorname {TIME} (t(n))=\operatorname {TIME} (g(t(n)))}$

より一般的には、Φ が抽象的な（ブルームの）複雑性測度であるとすると、任意のxに対して、Φに関して境界関数tとを持つ複雑性クラスが同一であるような、任意の全計算可能関数 gに対して、全計算可能関数tが存在する。 ${\displaystyle g(x)\geq x}$ ${\displaystyle g\circ t}$

意味合い

時間の複雑さの特殊なケースでは、これを次のように簡単に述べることができます。

すべてのxに対して となるような全計算可能関数に対して、となるような時間境界が存在する。${\displaystyle g:\,\omega \,\to \,\omega }$ ${\displaystyle g(x)\geq x}$ ${\displaystyle T(n)}$ ${\displaystyle {\mathsf {DTIME}}(g(T(n)))={\mathsf {DTIME}}(T(n))}$

空間計算量の特殊なケースについても同様です。

境界が非常に大きくなる場合があり（多くの場合、${\displaystyle T(n)}$ 非構成的である）、ギャップ定理はPやNPなどの複雑性クラスに対しては興味深い意味を持たず、^[5]時間階層定理や空間階層定理と矛盾しません。^[6]

参照

• ブルームのスピードアップ定理

参考文献

1. Fortnow, Lance ; Homer, Steve (2003年6月). 「計算複雑性の小史」(PDF) . Bulletin of the European Association for Theoretical Computer Science (80): 95– 133. 2005年12月29日時点のオリジナル(PDF)からのアーカイブ。
2. Trakhtenbrot, Boris A. (1967).アルゴリズムと計算の複雑性（講義ノート） . ノボシビルスク大学.
3. Borodin, Allan (1969). 「再帰関数の計算量クラスと計算量ギャップの存在」. Fischer, Patrick C.; Ginsburg, Seymour; Harrison, Michael A. (編).第1回ACM計算理論シンポジウム議事録, 1969年5月5日～7日, マリナ・デル・レイ, カリフォルニア州, 米国. 計算機協会. pp.  67– 78.
4. ボロディン、アラン（1972年1月）「計算複雑性と複雑性ギャップの存在」Journal of the ACM . 19 (1): 158– 174. doi : 10.1145/321679.321691 . hdl : 1813/5899 .
5. Allender, Eric W. ; Loui, Michael C. ; Regan, Kenneth W. (2014). 「第7章 複雑性理論」. Gonzalez, Teofilo ; Diaz-Herrera, Jorge ; Tucker, Allen (編). 『コンピューティングハンドブック 第3版 コンピュータサイエンスとソフトウェアエンジニアリング』. CRC Press. p. 7-9. ISBN 9781439898529幸いなことに、ギャップ現象は誰もが興味を持つような時間制限では発生しない。。
6. ジマンド、マリウス (2004). 計算複雑性：定量的視点. ノースホランド数学研究. 第196巻. エルゼビア. p. 42. ISBN 9780080476667。。