記述的複雑性理論

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

一階述語論理は、二項関係の推移閉包を計算する演算子を追加すると、表現力が大幅に向上する。結果として得られる推移閉包論理は、順序構造上の非決定性対数空間（NL）を特徴づけることが知られている。これを用いて、ImmermanはNLが補集合に関して閉じていること（すなわち、NL = co-NLであること）を示した。^{[ 12 ]}

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

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

SO-Kromとは、連言標準形の2階論理式で定義可能なブールクエリの集合であり、1階論理の量化子は全称であり、量化子を含まない部分はKrom形式である。つまり、1階論理式は選言の連言であり、各「選言」には最大で2つの変数しか含まれない。すべての2階Krom論理式は、存在量化子を含む2階Krom論理式と等価である。

SO-Kromは後継機能を持つ構造上のNLを特徴づける。^{[ 13 ]}

FO[LFP]は、単調式の不動点を表す最小不動点演算子による一階述語論理の拡張です。これにより、一階述語論理は再帰を表現する能力を獲得します。ImmermanとVardiによって独立に示されたImmerman –Vardiの定理は、FO[LFP]が順序構造上のPTIMEを特徴づけることを示しています。^{[ 14 ] [ 15 ]}

2025年現在しかし、順序付けされていない構造における PTIME を特徴付ける自然な論理が存在するかどうかは、まだ未解決である。

アビテブール・ヴィアヌの定理によれば、FO[LFP]=FO[PFP]となるのは、FO[LFP]=FO[PFP]となる場合のみであり、したがってP=PSPACEとなる場合のみである。この結果は他の固定点にも拡張されている。^{[ 8 ]}

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

SO-Hornは、SO式を選言標準形で定義できるブールクエリの集合であり、一階述語論理の量化子はすべて全称であり、量化子を含まない部分はHorn形式である。つまり、それはORの大きなANDであり、各「OR」では、おそらく1つを除くすべての変数が否定される。

このクラスは、後継関数を持つ構造ではPと等しい。 ^{[ 16 ]}

これらの式は、存在二階ホーン論理のプレネックス式に変換することができる。^{[ 13 ]}

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

存在式の補集合は普遍式であるため、co-NPは普遍的な二階述語論理によって特徴づけられることが直ちに導かれる。^{[ 6 ]}

したがって、無制限の2階論理は、多項式階層PHに等しい。より正確には、ファギンの定理の次の一般化がある。2階の存在量化子と全称量化子がk回交互に多項式階層のk番目のレベルを特徴付ける、前置正規形の式の集合。^{[ 18 ]}

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

多項式空間で計算可能なすべての問題のクラスであるPSPACEは、一階述語論理に表現力の高い部分不動点演算子を追加することで特徴づけることができる。

部分固定小数点論理（FO[PFP]）は、部分固定小数点演算子を備えた一階述語論理の拡張であり、式に不動点が存在する場合はそれを表し、存在しない場合は「false」を返します。

部分固定小数点論理は、順序構造上のPSPACEの特徴である。 ^{[ 20 ]}

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

高階変数を定義します。${\displaystyle i>1}$項数を持つ${\displaystyle k}$は任意の集合を表します${\displaystyle k}$-順序の要素のタプル${\displaystyle i-1}$それらは通常、大文字で表記され、指数として自然数を用いて次数を示します。高階論理は、高階変数に対する量化子を追加した一階論理式の集合です。したがって、ここでは一階論理の記事で定義された用語を改めて定義することなく使用します。

HO${\displaystyle ^{i}}$は、次数が最大で の変数を持つ式の集合です。${\displaystyle i}$. HO$\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}$同じ定量化で。したがってHO$\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}$

順序のすべての公式${\displaystyle i}$th は、まず変数に対する量化を記述する前置正規形の式と同等です。${\displaystyle i}$次、そして次数式${\displaystyle i-1}$通常の形式で。

HO は、基本関数のクラスELEMENTARYに等しい。より正確には、${\displaystyle {\mathsf {HO}}_{0}^{i}={\mathsf {NTIME}}(\exp _{2}^{i-2}(n^{O(1)}))}$塔を意味する${\displaystyle (i-2)}$ 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}}})}$