記述的複雑性理論

記述的複雑性は、計算複雑性理論および有限モデル理論の分野であり、複雑性クラスを、その中の言語を表現するために必要なロジックの種類によって特徴付けます。たとえば、多項式階層のすべての複雑性クラスの和集合である PH は、まさに2階論理のステートメントによって表現可能な言​​語のクラスです。複雑性と有限構造のロジックとのこの関係により、結果をある領域から別の領域に簡単に転送できるようになり、新しい証明方法が容易になり、主要な複雑性クラスが何らかの形で「自然」であり、それらを定義するために使用された特定の抽象マシンに結び付けられていないという追加の証拠が提供されます。

具体的には、各論理システムは、その中で表現可能な一連のクエリを生成します。クエリは、有限構造に制限されている場合、従来の複雑性理論の 計算問題に対応します。

記述的複雑性の最初の主要な結果は、 1974年にロナルド・ファギンによって示されたファギンの定理でした。この定理により、 NPはまさに存在二階述語論理の文で表現できる言語の集合であることが確立されました。つまり、関係、関数、および部分集合の全称量化を除いた二階述語論理です。その後、他の多くのクラスも同様に特徴付けられました。

論理形式を使用して計算問題を記述する場合、入力は有限構造であり、その構造の要素は議論の領域です。通常、入力は文字列（ビットまたはアルファベット全体）であり、論理構造の要素は文字列の位置を表すか、入力はグラフであり、論理構造の要素はその頂点を表します。入力の長さは、それぞれの構造のサイズによって測定されます。構造が何であれ、テストできる関係があると想定できます。たとえば、「xからyへのエッジがある場合にのみ真である」 (構造がグラフの場合)、または「文字列のn番目の文字が 1 である場合にのみ真である」などです。これらの関係は、1 階論理システムの述語です。また、それぞれの構造の特別な要素である定数もあります。たとえば、グラフの到達可能性をチェックする場合は、2 つの定数s (開始) とt (終了) を選択する必要があります。${\displaystyle E(x,y)}$${\displaystyle P(n)}$

記述的複雑性理論では、要素には完全な順序があり、要素間の等価性をチェックできると仮定することがよくあります。これにより、要素を数値として考えることができます。要素x は、となる要素yがある場合に限り、数値n を表します。これにより、プリミティブ述語「ビット」も得られます。ここで、の2進展開のk番目のビットのみが 1 である場合に限り、 は真です。(加算と乗算を、となる場合に限り、 が真であり、となる場合に限り、 が真である3 項関係に置き換えることができます。) ${\displaystyle (n-1)}$${\displaystyle y<x}$${\displaystyle ビット(x,k)}$${\displaystyle プラス(x,y,z)}$${\displaystyle x+y=z}$${\displaystyle 回(x,y,z)}$${\displaystyle x*y=z}$

後続関係と基本的な算術述語を持つ順序付けられた構造に限定すると、次の特性が得られます。

• 第一階述語論理はクラスAC ⁰を定義します。これは、深さが制限された多項式サイズの回路によって認識される言語であり、これは並行ランダムアクセスマシンによって一定時間で認識される言語に相当します。^[1]
• 対称的あるいは決定論的推移閉包演算子で拡張された一階述語論理は、対数空間で解ける問題Lを生み出す。 ^[2]
• 推移閉包演算子を用いた一階述語論理は非決定性対数空間で解ける問題NLを与える。 ^[3]
• 最小不動点演算子を用いた一階述語論理は、決定論的多項式時間で解ける問題Pを与える。 ^[3]
• 存在論的第二階論理はNPを生み出す。^[3]
• 普遍的二階述語論理（存在的二階述語量化を除く）はco-NPを生成する。^[4]
• 2階論理は多項式階層PHに対応する。^[3]
• 推移閉包（可換か否か）を持つ2階論理はPSPACE、すなわち多項式空間で解ける問題を生み出す。^[5]
• 最小不動点演算子を用いた2階論理は指数時間で解ける問題であるEXPTIMEを与える。 ^[6]
• 高階論理によって定義される複雑性クラスHOはELEMENTARYに等しい^[7]

回路の複雑性において、任意の述語を持つ一階述語論理は、 AC階層の最初のクラスであるAC ⁰と等しいことが示されます。実際、FOのシンボルから回路のノードへの自然な変換があり、そのノードはサイズnです。算術述語を持つシグネチャの一階述語論理は、AC ^{0ファミリの回路が}交代対数時間で構築可能な回路に制限されていることを特徴付けます。^[1]順序関係のみを持つシグネチャの一階述語論理は、スターフリー言語の集合に対応します。^{[8] [9]}${\displaystyle \forall ,\exists }$${\displaystyle \land}$${\displaystyle \lor}$

一階述語論理は、二項関係の推移閉包を計算する演算子を追加すると、表現力が大幅に向上します。結果として得られる推移閉包論理は、順序構造上の非決定性対数空間 (NL)を特徴付けることが知られています。これは、イマーマンによって、 NL が補集合に対して閉じていること (つまり、NL = co-NL) を示すために使用されました。 ^[10]

推移的閉包演算子を決定論的推移的閉包に制限すると、結果として得られる論理は順序付けられた構造上の対数空間を正確に特徴付けます。

後継関数を持つ構造では、NL は 2 次Krom 式によって特徴付けることもできます。

SO-Krom は、連言正規形の 2 階式で定義可能なブールクエリのセットです。1階の量指定子は普遍的で、式の量指定子のない部分は Krom 形式です。つまり、1 階式は選言の連言であり、各「選言」には最大 2 つの変数があります。すべての 2 階 Krom 式は、存在 2 階 Krom 式と同等です。

SO-Kromは後継関数を持つ構造上のNLを特徴づける。^[11]

順序付けられた構造では、1次の最小固定小数点ロジックがPTIME をキャプチャします。

FO[LFP]は、単調な式の固定点を表現する最小固定点演算子による一階論理の拡張である。これは、再帰を表現する能力によって一階論理を拡張する。ImmermanとVardiが独立に示したImmerman -Vardi定理は、FO[LFP]が順序構造上のPTIMEを特徴付けることを示す。^{[12] [13]}

2022 年現在、順序付けられていない構造上の PTIME を特徴付ける自然なロジックが存在するかどうかはまだ不明です。

アビテブール・ヴィアヌの定理は、あらゆる構造に​​おいてFO[LFP]=FO[PFP]が成り立つためには、FO[LFP]=FO[PFP]が成り立つ必要があることを述べています。つまり、P=PSPACEが成り立つ必要があるということです。この結果は他の不動点にも拡張されています。^[14]

後継関数が存在する場合、PTIME は 2 次ホーン式によって特徴付けることもできます。

SO-Horn は、選言正規形の SO 式で定義可能なブールクエリのセットです。このセットでは、第 1 階の量指定子はすべてユニバーサルであり、数式の量指定子のない部分はHorn形式です。つまり、これは OR の大きな AND であり、各 "OR" では、1 つを除くすべての変数が否定されます。

このクラスは後継関数を持つ構造上のPに等しい。 ^[15]

これらの式は、存在論的第二階ホーン論理における冠頭式に変換することができる。^[11]

1974年にロナルド・フェイギンが、NP複雑性クラスが存在二階論理で公理化可能な構造のクラスによって特徴付けられることを証明したことは、記述的複雑性理論の出発点となった。^{[4] [16]}

存在論理式の補語は普遍論理式なので、co-NPは普遍的な第二階論理によって特徴付けられることが直ちに分かります。^[4]

SO、つまり制限のない2階論理は、多項式階層 PHに等しい。より正確には、フェイギンの定理の次の一般化が得られる。2階の存在量化子と全称量化子がk回交互に現れる冠頭正規形の式の集合は、多項式階層のk番目のレベルを特徴付ける。 ^[17]

複雑性クラスの他のほとんどの特徴付けとは異なり、フェイギンの定理とその一般化は構造上の全順序を前提としていません。これは、存在的二階論理自体が、二階変数を使用して構造上の可能な全順序を参照するのに十分な表現力を持っているためです。^[18]

多項式空間PSPACEで計算可能なすべての問題のクラスは、より表現力豊かな部分固定小数点演算子を使用して第 1 階論理を拡張することによって特徴付けることができます。

部分固定小数点論理FO[PFP] は、部分固定小数点演算子を使用した第 1 階論理の拡張であり、式の固定小数点がある場合はそれを表し、ない場合は 'false' を返します。

部分的な固定小数点論理は順序構造上のPSPACEを特徴付ける。 ^[19]

2階論理は、1階論理と同じように推移閉包演算子によって拡張することができ、SO[TC]となる。TC演算子は2階変数を引数として取ることもできる。SO[TC]はPSPACEを特徴付ける。2階論理では順序を参照できるため、この特徴付けは順序構造を前提としない。^[20]

基本関数の時間計算量クラスELEMENTARY は、高階論理の式で認識できる構造の計算量クラスであるHOで特徴付けられます。高階論理は、高階量指定子を使用した第 1 階論理と第 2 階論理の拡張です。第 1 階と、指数関数のレベルで制限される時間の非決定性アルゴリズムの間には関係があります。 ^[21]${\displaystyle i}$${\displaystyle i-1}$

高階変数を定義します。 階数の変数はアリティを持ち、階数の要素の-組の任意の集合を表します。 これらは通常、大文字で書かれ、順序を示すために自然数を指数として使用します。 高階論理は、高階変数に量化を追加する一階式の集合です。 したがって、FOの記事で定義されている用語を再度定義せずに使用します。 ${\displaystyle i>1}$${\displaystyle k}$${\displaystyle k}$${\displaystyle i-1}$

HO は、最大 の位数の変数を持つ式の集合です。HO は、形式 の式のサブセットです。ここで、 は量指定子であり、 は同じ量指定を持つ位数の変数の組であることを意味します。したがって、HO は、で始まり、その後に位数の式が続く、位数 の量指定子の交代を持つ式の集合です。 ${\displaystyle ^{i}}$${\displaystyle i}$${\displaystyle _{j}^{i}}$${\displaystyle \phi =\exists {\overline {X_{1}^{i}}}\forall {\overline {X_{2}^{i}}}\dots Q{\overline {X_{j}^{i}}}\psi }$${\displaystyle Q}$${\displaystyle Q{\overline {X^{i}}}}$${\displaystyle {\overline {X^{i}}}}$${\displaystyle i}$${\displaystyle _{j}^{i}}$${\displaystyle j}$${\displaystyle i}$${\displaystyle \exists }$${\displaystyle i-1}$

テトレーションの標準表記法、および、を時間とともに使用すると、${\displaystyle \exp_{2}^{0}(x)=x}$${\displaystyle \exp_{2}^{i+1}(x)=2^{\exp_{2}^{i}(x)}}$${\displaystyle \exp _{2}^{i+1}(x)=2^{2^{2^{2^{\dots ^{2^{x}}}}}}}$${\displaystyle i}$${\displaystyle 2}$

th 次のすべての式は冠頭正規形の式と同等です。ここで、最初にth 次の変数に対する量化を記述し、次に正規形の th 次の式を記述します。 ${\displaystyle i}$${\displaystyle i}$${\displaystyle i-1}$

HO は、初等関数のクラスELEMENTARYに等しい。より正確には、 は 2の塔を意味し、 で終わり、 は定数である。この特殊なケースは であり、これはまさにフェイギンの定理である。多項式階層の神託機械を使用すると、${\displaystyle {\mathsf {HO}}_{0}^{i}={\mathsf {NTIME}}(\exp _{2}^{i-2}(n^{O(1)}))}$${\displaystyle (i-2)}$${\displaystyle n^{c}}$${\displaystyle c}$${\displaystyle \exists {\mathsf {SO}}={\mathsf {HO}}_{0}^{2}={\mathsf {NTIME}}(n^{O(1)})={\color {Blue}{\mathsf {NP}}}}$${\displaystyle {\mathsf {HO}}_{j}^{i}={\color {Blue}{\mathsf {NTIME}}}(\exp _{2}^{i-2}(n^{O(1)})^{\Sigma _{j}^{\mathsf {P}}})}$

• イマーマン、ニール（1999）。記述的複雑性。シュプリンガー。ISBN 0-387-98600-6. OCLC  901297152.

• ニール・イマーマンの記述的複雑性のページ（図を含む）