記述計算量

記述計算量（きじゅつけいさんりょう、）は、有限モデル理論の一種であり、計算複雑性理論と数理論理学の一分野である。複雑性クラスを言語で表現するのに必要とされる論理の種類によって特徴付けることを目的とする。例えば、PHは二階述語論理の論理式で表現される言語のクラスと正確に対応している。このような複雑性と論理の繋がりによって、2つの分野の間で容易に変換が可能となり、新たな証明手法を生み出したり、ある複雑性クラスが本質的なものであって、特定の抽象機械に結びつくものではないことを示すことができる。
概要.
特に、それぞれの論理体系は、その中で表現可能なクエリの集合を生み出す。クエリは計算複雑性理論における計算問題と対応している。
記述計算量の最初の成果として、1974年にロナルド・フェイギンが示した Fagin の定理がある。これは、NPが存在量化二階述語論理の論理式で表現可能な言語の集合と正確に対応していることを示した。存在量化二階述語論理とは、関係・関数・部分集合について全称量化を行わない二階述語論理である。他の多くのクラスについても、主に Neil Immerman によって同様の特徴付けがなされた。以下に主なものを列挙する。