記述計算量
特に、それぞれの論理体系は、その中で表現可能なクエリの集合を生み出す。クエリは計算複雑性理論における計算問題と対応している。
記述計算量の最初の成果として、1974年にロナルド・フェイギンが示した Fagin の定理がある。これは、NPが存在量化二階述語論理の論理式で表現可能な言語の集合と正確に対応していることを示した。存在量化二階述語論理とは、関係・関数・部分集合について全称量化を行わない二階述語論理である。他の多くのクラスについても、主に Neil Immerman によって同様の特徴付けがなされた。以下に主なものを列挙する。
一階述語論理はクラス FO(あるいは AC)を定義し、その言語は定数深さの多項式サイズ回路で認識される。これは並行ランダムアクセス機械(CRAM、CRCW型のPRAMにほぼ相当するモデル)で定数時間で認識される言語と等価である。
一階述語論理に可換な推移閉包演算子を追加したものは、SL に相当する。これは対数領域で解ける問題のクラス L と等しい。
一階述語論理に推移閉包演算子を追加したものは、NL に相当する。
線形順序が存在する場合、最小不動点演算子を持つ一階述語論理が P に相当する。
存在量化二階述語論理は NP に相当する(上述の通り)。
二階存在量化をのぞいた全称二階述語論理は co-NP に相当する。
二階述語論理は PH に相当する。
推移閉包演算子を持つ二階述語論理は PSPACE に相当する。
最小不動点演算子を持つ二階述語論理は EXPTIME に相当する。