MAX<'+>(2)公式改名的复杂性

来源 :贵州大学 | 被引量 : 0次 | 上传用户:wan6415383aa
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
一个CNF公式F称为极小不可满足的(MU),如果F是不可满足,并且在F中删去任意一个子句后所得到的公式是可满足的。一个MU中的公式F称为最大的,如果对于任意一个子句f∈F且对于任意一个文字L,-L,L f,将L添加到子句f中,公式F变为可满足的。最大的极小不可满足公式类记作MAX,MAX(k)=MU(k)∩MAX。公式F的一个改名是一个定义在var(F)上的函数Ψ,使得对每个变元x,Ψ(x)∈{x,-x);公式F的一个变元改名是var(F)上的一个置换;公式F的一个文字改名是一个变元改名和一个改名的组合。以上这三种改名不改变公式的可满足性。改名规则在创建有效的满足性算法和简化某些消解难例的证明中起到了重要作用。许道云教授已经证明:MU(k)中的变元和文字改名都等价于图同构的判定问题,而图同构的判定问题是NP问题。最近,许道云教授找到了一个极小不可满足公式的子类——MAX<+>公式,该类公式的变元和文字改名的判定问题可以在多项式时间内完成,并指出MAX<+>(1)公式的改名判定时间是O(n<2>)。 本文基于上述结论,利用Hans.Kleine Brining教授提出的分裂技术,先对一些满足特殊条件的MAX<+>公式的结构进行了分析,发现了一些规律。之后,利用这些规律,再对MAX<+>(2)公式的结构进行了分析,发现任何一个MAX<+>(2)公式的结构必然具有如下情况之一: (1)有两个全出现变元,且每个变元在公式F的正负出现次数至少为2; (2)有唯一的全出现变元; (3)没有全出现变元,但有1到3个准全出现变元,且每个变元在公式F的正负出现次数至少为2; (4)没有全出现变元和准全出现变元,但有唯一的一对匹配变元对,并且在这对变元中至少有一个变元在公式F中的正负出现次数至少为2。 这些结构特点保证了两个MAX<+>(2)公式是否有改名函数的问题可以在O(n<2>)时间内完成。本文给出了相应的算法,并进行了证明。
其他文献
随着人工神经网络的深入研究,人工神经网络方法已在许多领域获得成功运用。神经网络的主要特点体现在其具有信息处理的并行性、分布式的信息存储、自组织性和自适应性、具有
在知识发现的诸多理论之中,粗糙集理论是一种对处理复杂数据较为有效的方法,它并不要求提供问题所需处理的数据集之外的任何先验信息,并且与其它的处理不确定性问题的理论有
本文针对目前基于内容的图像检索算法在算法效率和准确性方面存在的局限性,探讨了基于内容的图像检索技术中若干重要问题,提出了一种注意力驱动的两阶段图像检索方案,着重研
视觉跟踪是虚拟现实、人机交互、视觉监控等领域内的关键技术,具有巨大的应用前景。由于存在遮挡、图像处理复杂等特点,视觉跟踪的实时性一直难以提高,实时性是目前视觉跟踪技术
移动边缘计算(Mobile Edge Computing,MEC)技术作为云计算服务模式在边缘网络中的扩展,能够在边缘网络中支持资源密集型应用,并为用户提供实时服务,解决了传统云计算中心提供
随着计算机网络技术的迅速发展,互联网已成为人们日常生活中不可或缺的一部分,网络给人们带来方便的同时其安全性也经受着巨大的挑战,数据加解密技术作为信息安全领域的关键技术
本文提出了一种改进的支持向量分类方法和一种针对支持向量机的增量学习算法。根据支持向量机中支持向量不会出现在两类样本集间隔以外的正确划分区的理论,通过引入类质心,类半
进入二十一世纪以来,因特网迅速发展,逐渐普及。随之而来的网络娱乐业也进入了一个迅猛发展期,其中网络游戏扮演了重要角色。2001年,全球的游戏市场达到165亿美元,超过电影160亿美
随着信息技术的迅速发展,特别是Internet的普及,网页数量呈海量增长。由于网页中的内容大部分是文本信息,因此如何根据网页中的文本信息自动分类成为目前研究的重要课题。由
电力工业的发展促进了发电机组单机容量和参数不断增加,其自动化程度越来越高,对控制系统的控制品质也提出了更高的要求。掌握被控对象的数学模型和建模后控制系统的设计,是过程