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