摘要: 本文从模型等价归约的角度研究了不同NP逻辑系统的表示能力。我们所说的NP逻辑系统，是指模型存在问题（即可满足问题）在NP中的逻辑系统。在这个定义下，命题公式类PF,命题公式的合取范式类CNF，每一子句最多包含k个文字(k>=3)的kCNF公式类，回答集语义下的逻辑程序类LP以及只带存在量词的量化布尔公式类 PF都是NP逻辑系统。根据相关文献已知: 1.PF,CNF,LP, PF 对于等价性具有相同的表示能力。即，对任意上述两个系统S1，S2，存在一种转换将S1的公式翻译成S2的公式，并使得两个公式之间的模型是相同的。2.从(k+1)CNF到kCNF，不存在保等价性的归约，而且CNF的表示能力严格强于kCNF. 3.从PF到CNF，不存在保持等价性的多项式空间的翻译。4.在P不是NC1/Poly子集的复杂性猜想下，不存在保等价的从LP到PF的多项式空间翻译。
不难看出，即便是模型存在问题在同一复杂性类中的逻辑系统，其表示能力也非常不同。由于在一些NP逻辑系统中，不存在保等价性的多项式空间翻译，因此我们很自然地考虑在某种保持弱等价性的条件下考察这些系统之间的(多项式时间/空间)转换。由赵希顺及Hans Kleine Buening提出的模型等价归约就是这样一种保持弱等价性的归约。简单地说，一个系统S可以被模型等价地归约到S'上，如果每一个S的公式F，都可被转换成一个S'的公式F',并且在F与F'的模型上存在着一个多项式时间可计算的一一对应转换。在多项式时间的模型等价归约下，PF,CNF,3CNF,LP具有相同的表示能力。然而，在广泛接受的NP不是P/Poly子集的复杂性猜想下, PF相对于PF仍有严格强的表示能力，也即是说，甚至似乎不存在从 PF到PF的多项式空间的模型等价归约。因此，赵希顺与Hans Kleine Buening提出了以下问题：在多项式模型等价归约的条件下， PF是一个极大的(表示能力最强)NP逻辑系统吗？在本文中，我们证明了：(1)对于所有模型检测问题(即检测一个解释是否为给定公式模型)在NP中的NP逻辑系统， PF相对于多项式时间模型等价归约是极大的；(2) 对于所有模型检测问题在P中的NP逻辑系统，PF相对于多项式时间模型等价归约是极大的；(3)在一些复杂性猜想下，存在着多项式空间模型等价归约下与 PF不可比较、或者严格强于 PF的逻辑系统。最后，在一些复杂性猜想下，我们猜测不存在模型等价归约下所谓最强的NP逻辑系统。