有限モデル理論
記述計算量の考え方によって、計算複雑性理論と数理論理学の成果の交流が可能となり、標準的な複雑性クラスが「自然」なものであるという証拠も与える。Neil Immerman は、「数理論理学の歴史の中でも、有限構造に関する研究が最も興味深く...さらに言えば、コンピュータ上のオブジェクトは常に有限である。計算の研究には、有限構造の理論が必要である」と述べている。
また、有限モデル理論の重要な帰結の一つに、対象 x の性質 P(x) はほとんどの対象において当てはまるものであるか、ほとんどの対象において当てはまらないものであるかに分類されるという法則(Zero-One Law)がある。たとえば、サイズが n 以下のグラフの性質について考えるとき、対象が連結グラフである確率は n が無限大に近づくにつれて 1 に近づく。逆に、対象が孤立点を含んでいる確率は 0 に近づく。Zero-One Lawは、多項式時間でチェック可能な任意のグラフの性質について、性質を満たす対象の比率が 1 か 0 のどちらかに近づいていくことを主張する。この法則は、大規模な有限構造についての乱択アルゴリズムに影響を及ぼす。
有限モデル理論では、論理の有限な制限についても研究する。例えば、変項数を k 個に制限された一階述語論理などである。