冯世光 王克诩 赵希顺

1 引言

有穷模型论以有穷结构为主要研究对象，其发展受到了计算复杂性理论、数据库理论和形式语言的影响。1950 年B.Trakhtenbrot 证明了在有穷模型上一个公式的可满足性问题是不可判定的（[17]），标志着有穷模型论的诞生。描述复杂性理论是有穷模型论的一个分支，它从逻辑的角度对计算复杂性进行研究。计算复杂性理论关心的是解决一个问题所需要的时间和空间资源，而描述复杂性则主要研究定义一个问题所需要的最小逻辑的表达能力。判断一个结构A是否满足公式φ的复杂性有三种：(1)数据复杂性，即公式φ给定，结构A作为问题的输入；(2)表达式复杂性，即结构A给定，公式φ作为问题的输入；(3)混合复杂性，即结构A和公式φ同时作为问题的输入。

本文主要考虑数据复杂性，一般随着表达能力的增强一个逻辑的数据复杂性也会变大。例如一阶逻辑的数据复杂性在L 中，但它不能表达图的三着色问题。存在型二阶逻辑（∃SO）可以表达图的三着色问题，但它的数据复杂性是NP 完全的。在描述复杂性中用“刻画”来定义这种表达能力与数据复杂性之间的关系。称逻辑L刻画复杂性类C，则他们满足：(1)逻辑L的数据复杂性在C中；(2)复杂性类C中的问题在逻辑L中可表达。

有了刻画的概念之后，可以通过比较不同逻辑的表达能力来研究他们所刻画的复杂性类之间的关系，即如果逻辑L1刻画复杂性类C1，逻辑L2刻画复杂性类C2，则C1=C2当且仅当L1≡L2。（[5]）1974 年，R.Fagin 证明了∃SO 能够刻画NP（[6]），这一定理的证明开启了描述复杂性研究的先河。……