可满足公式到MU(1)公式的扩张

来源 :贵州大学 | 被引量 : 0次 | 上传用户:kevin_0713
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
经典逻辑中的SAT问题是指布尔表达式的可满足性问题,它是计算机科学中的核心问题。SAT问题是NP完全问题,从理论上说,SAT问题不能在多项式时间内解决,它超出了现代计算机的能力。所以,SAT问题是计算机科学发展中的“瓶颈”问题,计算机科学家们一直都在寻求各种快速策略和方法试图改进SAT问题的求解。 极小不可满足公式的研究是近年来兴起的关于SAT问题的一个热点方向。个CNF公式(CNF公式是有限个子句的合取)F称为极小不可满足的(MU),如果F是不可满足,并且在F中删去任意一个子句后所得到的公式是可满足的。MU(k)表示子句数与变元数的差为k的极小不可满足公式的类。Kleine Buning.H等人的研究结果表明:如果k≤0,则公式不是极小不可满足的,也就是说,所有极小小可满足公式其子句数必定大于公式中的变量个数。 在本文中,我们将给出一个在多项式时间内判定可满足公式到MU(1)公式扩张问题的算法。关于公式扩张问题,Kleine Buning H和Zhao X S已经做出了若干结果,他们得出:Horn公式到MU(1)公式的扩张问题可在多项式时间内判定,问题MU-EXT[ext=t]为DP-难,问题MU-EXT[ext=1]在P(NP[logn]之中,问题MU-EXT[ext=t,defi=k]可在多项式时间内判定,这里记MU-EXT[ext=t,defi=k]={F∈CNF|(?)G:F+G∈MU(k),var(G)(?)var(F),|G|=t}。在本论文中,我们考虑对一个给定可满足CNF公式F,是否存在公式G使得F+G∈MU(1)(var(G)(?)var(F))并给出这个问题的多项式时间判定算法。
其他文献
在高层建筑施工的过程中,高层建筑具有资金投入较大,作业面较为狭窄,施工工期较长的特点,这就对施工技术提出了更高的要求,因此,高层建筑施工要点显得尤为重要。本文提出了高层结构
期刊
植物病毒已对生物界构成重大威胁与危害,揭示植物病毒的传染机理,探讨预防与控制的手段,具有十分重要的意义.本文通过建立数学模型,对植物传染病模型进行定性分析、定量分析和数
本文分五章:第一章为引言;第二章研究一类具有奇异积分项的Boussinesq方程的Cauchy问题的局部解的存在惟一性;第三章通过积分估计证明第二章所述问题的整体解的存在惟一性;第四章
本文对两类Z3旋转不变平面五次多项式扰动微分系统的极限环的数量和分布进行了研究。通过结合奇点、双同宿环、异宿环分支理论给出了扰动系统具有同宿环或异宿环的条件,再通过
人民生活水平的提高给排水工程施工技术提出了更高的要求,提高施工质量,需要施工人员不断学习,提高施工的技术水平,确保施工的安全、质量、稳定、灵活性,满足高层建筑给排水
期刊
随着我国人民生活水平的不断提高,住宅能耗占全国能源消费总量的比例也逐年增加,加强住宅工程建筑节能设计,刻不容缓。本文介绍了住宅建筑节能设计的关注要点,具体分析了住宅建
期刊
生物图像信息检测与识别技术因其重要性而得到世界各国广泛关注并广泛应用在各个领域。当前,生物医学技术的发展、生物信息学的发展、公共安全的需要为生物图像信息检测与识别
自1984年求解线性规划问题的Karmarkar算法发表以来,关于线性规划和凸非线性规划的内点法的研究受到了极大重视,产生了丰富的研究成果. 冯果忱、于波、林正华提出了解非凸Br