【摘 要】
：
通过一个恰当的归约变换,可以将一个CNF公式变换为另一个具有某种特殊结构或性质的公式,使其两者具有相同的可满足性。一个典型的归约是将一般的CNF公式变换为3-CNF公式。通
【基金项目】
：
supported by the National Natural Science Foundation of China(No.600863005)
论文部分内容阅读
通过一个恰当的归约变换,可以将一个CNF公式变换为另一个具有某种特殊结构或性质的公式,使其两者具有相同的可满足性。一个典型的归约是将一般的CNF公式变换为3-CNF公式。通过构造一些恰当的工具,可以将公式类变换为所要求的正则类。极小不可满足公式具有一个临界特征,公式本身不可满足,从原始公式中删去任意一个子句后得到的公式可满足。我们提供了一种归约技术,通过构造恰当的极小不可满足公式作为工具,将公式类变换为具有正则结构的公式类。研究正则结构的公式的复杂性及性质很有意义。如,将一个从3-CNF公式变换为(34)-CNF公式,这里(34)-CNF公式是指公式中每个子句的长度恰为3,每个变元出现的次数恰为4。因此,(34)-SAT是一个NP-完全问题,并且正则二部图的诸多良好性质对于研究正则结构的SAT问题具有许多潜在的作用。
其他文献
在回顾终身教育与终身体育概念形成历史的基础上,反思了当前高校体育教育与终身体育教育观相背离的典型现状:1)过分注重技能学习和体能增长,忽视学生精神生活的需要;2)脱离现
中学教育的核心是学习能力的培养,但一个国家的文明程度在很大程度上取决于人的整体素质,但人们在素质教育过程中往往忽视对后进生的教育,对后进生进行转化应着重实施心理障
"自然之道"在魏晋时代包含着浓郁的人文关怀和清明的理性精神。崇尚自然之道对嵇康的音乐美学思想产生了重要影响。在《声无哀乐论》中,嵇康以理性的科学的态度,推翻了从西周
１．研究目的为对大学英语考试（ＣｏｌｅｇｅＥｎｇｌｉｓｈＴｅｓｔ，简称ＣＥＴ）的效度进行检验，全国大学英语四、六级考试委员会与英国文化委员会（ＢｒｉｔｉｓｈＣｏｕｎｃｉｌ）合作对ＣＥＴ中的各部分试题进行了为期三年的效度研究，其中包括了对ＣＥＴ阅读理解...
介绍了利用UG NX4.0软件进行注塑模具设计的方法。通过具体实例,阐述了如何利用UG NX4.0软件的参数化实体建模技术实现模具型腔、型芯的设计,模具装配、干涉分析、生成二维图
目前,我国农业和农村经济、社会事业取得了长足的发展。随着粮食的持续增产,粮食生产总量已基本满足消费需求,但是由于过分依赖施用化肥、农药来增加产量,以及重金属污染等,
目的:综述近年来有关复发性阿弗他溃疡与饮食关系的研究进展。方法:以国内外研究复发性阿弗他溃疡与饮食关系的代表性论文为依据,进行分析、整理和归纳。结果:复发性阿弗他溃
运用问卷调查、文献资料和数理统计等方法对大学生休闲教育内容进行分析,并且从休闲教育内容着手,基于休闲体育视角,认为构建适合大学生的休闲教育内容顺应时代的要求,对大学
本文介绍了一种简便易行的正态性检验方法——W检验,并结合两个实例进行了试卷分析。