首页> 中文会议>第二届两岸逻辑教学学术会议 >Size of Models and Complexity of QBF with Fixed Maximal Deficiency

Size of Models and Complexity of QBF with Fixed Maximal Deficiency

页面导航

摘要
著录项
相似文献
相关主题

摘要

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

著录项

来源
《第二届两岸逻辑教学学术会议》|2006年|368-385|共18页
会议地点南京
作者
Hans Kleine Biining; Xishun Zhao;
展开▼
作者单位

中国逻辑学会;

江苏省逻辑学会;

南京大学;

展开▼
会议组织
正文语种
原文格式 PDF
中图分类判断、命题;
关键词
最大亏度; 量化布尔公式; 多项式算法;

相似文献

中文文献
外文文献
专利

1. 基于SIZER的变频驱动系统谐波分析 [C] . 徐丽 . 2014西门子工业专家会议 . 2014
2. The take-over of small and medium sized commercial banks.“A Case Study of China Baoshang Bank.” [A] . Nicole Mwaita Nyanjowa . 2020

Size of Models and Complexity of QBF with Fixed Maximal Deficiency

摘要

著录项

相似文献

相关主题

期刊订阅