Size of Models and Complexity of QBF with Fixed Maximal Deficiency

摘要：

本文证明了：对于最大亏度为k的量化布尔公式，如果它是真的，则存存集合U，其中含有不超过24k/3个全称变元，且存存模型M，其中每一个布尔函数都可表示为U上的命题公式。也就是说，这样的公式都有长度很短的公式.于是.对于最大亏度为k的量化布尔公式.它们的真假问题可在非确定多项式时间内判定。但到目前为止我们还没有找到多项式算法。 只是对于一些重要的子类，如QEHORN(即每个子句中存在文字组成一个HORN子句)和QE2CNF(即每个子句中最多含有两个存在文字)，当固定最大亏度时，真假问题可在多项式时间内判定。

关键词： 最大亏度 量化布尔公式 多项式算法

作者: Hans Kleine Biining Xishun Zhao

作者单位: Department of Computer Science，Universitǎt Paderborn 33095 Paderborn(Gemany) Institute of Logic and Cognition，Sun Yat-sen University 510275 Guangzhou，(P.R.China)

会议类型: 国内会议

会议名称: 第二届两岸逻辑教学学术会议

会议地点: 南京

会议语种:英文

页码: 368-385

在线出版日期: 2006-10-28（万方平台首次上网日期，不代表论文的发表时间）