Canonical Logic Programs are Succinctly Incomparable with Proposition Formulas

4月16日下午，来自中山大学的沈榆平老师为我们做了题为“典范逻辑程序与命题逻辑公式的简洁性不可比”的报告。沈老师首先介绍了简洁性的直观背景，有些逻辑的表达力和复杂性都是等价的，但简洁性却不一样，比如通常的命题逻辑公式与单纯的合取范式公式相比，有一些性质用普通的命题公式表示很简单，但如果限定只用合取范式公式表示却要指数长。抽象的说，一个逻辑比另一个逻辑简洁是指，有一个问题在前者中可以多项式表示，而在后者中却需要指数长的公式才能表示。有一些逻辑它们相互之间的简洁性不可比，比如合取范式与析取范式之间就不可比。
然后沈老师细致的介绍了典范逻辑程序的语法及其回答集语义，它是一种非单调的逻辑，沈老师通过两个例子解释了它为什么是非单调的及其与命题逻辑的差别。一个二进制序列可以表示一系列变元，一个问题可以用一集二进制序列表示。Lifschitz和Razborov曾证明，在某种假设下，PATH问题（它在P问题中是最难的）在典范逻辑程序中可以多项式表示而在命题逻辑中却需要指数表示，沈老师今天报告的结果是另一个方向，可以构造一个PARITY问题，即，在给定字母表下，判定二进制序列中所包含的1的个数为奇数，这个问题的计算复杂性非常低，它是线性的，但它在典范逻辑程序中的表示却是指数的，而在命题逻辑中的表示是多项式的，这意味着，在把命题逻辑公式向典范逻辑程序的翻译过程中，对于某些问题，如果不引进新的变元的话，公式长度的指数增长是不可避免的。沈老师的结果与Lifschitz,Razborov的结果合起来显示，典范逻辑程序与命题逻辑的简洁性不可比，虽然二者的表达力完全一样，复杂性也完全一样，都是NP完全的。这同时也从另一个角度揭示了计算复杂性与描述复杂性之间的微妙关系。
    报告结束后，各位老师和同学就对典范逻辑程序进行公理化的可能性、简洁性问题分类的刻画标准等问题进行了讨论。

（撰稿人：李熙）