構造複雑性理論

計算機科学における計算複雑性理論において、構造複雑性理論、あるいは単に構造複雑性と呼ばれるものは、個々の問題やアルゴリズムの計算複雑性ではなく、複雑性クラスの研究です。様々な複雑性クラスの内部構造と、異なる複雑性クラス間の関係の両方を研究します。^[1]

歴史

この理論は、この種の最初の、そして今でも最も重要な問題であるP = NP問題を解こうとする（未だに失敗に終わっている）試みの結果として現れた。研究の大部分は、PがNPと等しくないという仮定と、複雑性クラスの多項式時間階層が無限であるというより広範な仮説に基づいて行われている。^[1]

重要な結果

圧縮定理

圧縮定理は、計算可能な関数の複雑さに関する重要な定理です。

定理は、計算可能な境界を持ち、すべての計算可能な関数を含む最大の複雑性クラスは存在しないことを述べています。

空間階層定理

空間階層定理は、特定の条件下では、決定性マシンと非決定性マシンの両方が（漸近的に）より多くの空間でより多くの問題を解くことができることを示す分離結果です。例えば、決定性チューリングマシンは、空間n log nで解く方が、空間nで解くよりも多くの決定問題を解くことができます。時間に関するやや弱い類似の定理は、時間階層定理です。

時間階層定理

時間階層定理は、チューリングマシンにおける時間制限付き計算に関する重要な定理です。非公式には、これらの定理は、より多くの時間を与えられたチューリングマシンはより多くの問題を解けることを示しています。例えば、n ²時間で解けるのにn時間では解けない問題があります。

ヴァリアント・ヴァジラニ定理

ヴァリアント＝ヴァジラニの定理は、計算複雑性理論における定理です。レスリー・ヴァリアントとヴィジェイ・ヴァジラニは、1986年に発表した論文「NPは一意解の検出と同じくらい簡単」でこの定理を証明しました。 ^{[2]この定理は、}一義的SAT（Unambiguous-SAT）に対する多項式時間アルゴリズムが存在する場合、NP = RPとなることを述べています。この証明は、後に理論計算機科学における多くの重要な応用に用いられたマルムリー＝ヴァジラニの孤立補題に基づいています。

シプサー・ラウテマンの定理

シプサー・ラウテマンの定理またはシプサー・ガックス・ラウテマンの定理は、有界誤差確率多項式(BPP) 時間は多項式時間階層、より具体的には Σ ₂ ∩ Π ₂に含まれると述べています。

サヴィッチの定理

1970年にウォルター・サヴィッチによって証明されたサヴィッチの定理は、決定論的空間計算量と非決定論的空間計算量との関係を示している。これは、任意の関数に対して、 $f\in \Omega (\log(n))$

{\mathsf {NSPACE}}\left(f\left(n\right)\right)\subseteq {\mathsf {DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right).

戸田の定理

戸田の定理は、戸田誠之助が論文「多項式時間階層は多項式時間階層と同じくらい難しい」（1991年）で証明し、1998年のゲーデル賞を受賞した結果である。この定理は、多項式階層全体PH がP ^PPに含まれることを述べている。これは、PH が P ^#Pに含まれるという密接に関連する命題を示唆している。

インメルマン・シェレプセニの定理

イマーマン・シェレプチェニの定理は、 1987年にニール・イマーマンとロバート・シェレプチェニによって独立に証明され、2人は1995年のゲーデル賞を共同受賞しました。この定理の一般形では、任意の関数s ( n )≥logn に対してNSPACE ( s ( n )) = co-NSPACE( s ( n )) が成り立つと述べています。この結果は、NL = co-NL と同等に述べられます。これはs ( n )=lognの特別なケースですが、標準的なパディングの議論によって一般定理が導かれます^[^要出典^]。この結果により、2番目の LBA 問題が解決されました。

研究テーマ

この分野の主な研究の方向性としては以下が挙げられる^[1]。

複雑性クラスに関する様々な未解決問題から生じる含意の研究
さまざまな種類のリソース制限付き縮小とそれに対応する完全な言語の研究
データの保存とアクセスに関するさまざまな制限とメカニズムの結果の研究

参考文献

^ abc Juris Hartmanis、「構造複雑性理論の新展開」（招待講演）、Proc. 15th International Colloquium on Automata, Languages and Programming、1988年（ICALP 88）、Lecture Notes in Computer Science、vol. 317（1988）、pp. 271-286。
^ Valiant, L.; Vazirani, V. (1986). 「NPは一意解の検出と同じくらい簡単だ」(PDF) .理論計算機科学. 47 : 85–93 . doi : 10.1016/0304-3975(86)90135-0 .

[jha-1] Juris Hartmanis、「構造複雑性理論の新展開」（招待講演）、Proc. 15th International Colloquium on Automata, Languages and Programming、1988年（ICALP 88）、Lecture Notes in Computer Science、vol. 317（1988）、pp. 271-286。

[2] Valiant, L.; Vazirani, V. (1986). 「NPは一意解の検出と同じくらい簡単だ」(PDF) .理論計算機科学. 47 : 85–93 . doi : 10.1016/0304-3975(86)90135-0 .