Canonical logic programs are succinctly incomparable with propositional formulas

• 作 者: 赵希顺 沈榆平
• 机 构: 中山大学
• 出 处: 2014年南开数理逻辑研讨会
• 发表日期: 2014年11期

　　Canonical(logic)programs(CP)refer to normal logic programs(LP)augmented with connective not not.In this paper we address the question of whether CP are succinctly incomparable with proposition-al formulas(PF).Our main result shows that the PARITY problem,which can be polynomially represented in PF,only has exponential representations in CP.In other words,PARITY separates PF from CP.Simply speaking; this means that exponential size blowup is generally inevitable when translating a set of formulas in PF into an equivalent program in CP(without introducing new variables).Furthermore,since it has been shown by Lipschitz and Razborov that there is also a problem which separates CP from PF(assuming P(≦)NC1=poly),it follows that the two formalisms are indeed succinctly incomparable.In addition,we show that PARITY separates logic programs with cardinality constraints and choice rules(CC)from CP.Moreover,assuming P(≦)NC1=poly,CP and definite causal theories(DT)are succinctly incomparable,two-valued programs(TV)are strictly more succinct than CP and DT.