構造複雑性理論

コンピュータサイエンスの計算複雑性理論において、構造複雑性理論または単に構造複雑性は、個々の問題やアルゴリズムの計算複雑性ではなく、複雑性のクラスの研究です。さまざまな複雑性のクラスの内部構造と、異なる複雑性のクラス間の関係の両方の研究が含まれます。^[1]

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

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

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

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

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

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

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

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

${\displaystyle {\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 ) ≥ log  nに対してNSPACE ( s ( n )) = co-NSPACE( s ( n ))が成り立つことを述べています。結果は、NL = co-NL と同等に述べられます。これはs ( n ) = log nの特殊なケースですが、標準的なパディングの議論によって一般定理が導かれます^[要出典]。この結果により、2番目の LBA 問題が解決しました。

この分野の主な研究の方向性としては、以下のものがある。^[1]

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