19/03/11 20:49:02.33 NUGiaq8/.net
>>178
つづき
近年、二階述語論理は一種の回復の途上にある。この傾向をもたらしたのは George Boolos による二階の量化の解釈であり、彼は一階の量化と同じドメインでの複数形の量化として二階の量化を解釈した。
Boolos はさらに一階述語論理では記述できない文を例に挙げ、完全な二階述語論理の量化でのみそれらを表現可能であるとした。
計算複雑性理論への応用
有限な構造についての二階述語論理の各種形式の表現能力は、計算複雑性理論と密接に関係している。
二階述語論理を前提として次のような複雑性クラスを説明できる。
・NP は、存在量化二階述語論理で表現できる言語の集合である（F