最坏情况下X2SAT问题的上界

来源 :计算机研究与发展 | 被引量 : 0次 | 上传用户：lhk4444

【摘要】

：

最坏情况下XSAT问题上界的研究已成为一个热门的研究领域.针对XSAT的泛化问题X2 SAT提出了算法X2SAT-N,该算法首先利用简化算法Simplify对公式进行化简,然后通过分支树的方法

【作者】

：

周俊萍姜蕴晖殷明浩

【机构】

：

东北师范大学计算机科学与信息技术学院

【出处】

：

计算机研究与发展

【发表日期】

：

2014年3期

【关键词】

：

最坏情况上界复杂性分析分支树 worst case upper bounds X2SAT complexity analysis branching tr

【基金项目】

：

国家自然科学基金项目（60803102,61070084,11226275）,吉林省自然科学基金项目（201215006）,中央高校基本科研业务费专项资金项目（1lQNJJ006,11CXPYOlO）,高等学校博士学科点专项科研基金项目（20120043120017）

下载到本地 , 更方便阅读

下载此文赞助VIP

声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架

论文部分内容阅读

最坏情况下XSAT问题上界的研究已成为一个热门的研究领域.针对XSAT的泛化问题X2 SAT提出了算法X2SAT-N,该算法首先利用简化算法Simplify对公式进行化简,然后通过分支树的方法对不同情况的子句进行分支.证明了该算法可以将X2SAT问题的时间复杂度由目前最好的O（1.451 1n）提高到O（1.420 3n）,其中n为X2 SAT公式中变量的数目.X2SAT问题实例的大小不仅依赖于变量的数目还依赖于公式的长度,时间复杂性是根据问题实例的大小所组成的函数计算所得.因此又提出了算法X2SAT-L

其他文献

生态林业发展中现代林业技术推广探讨

我国林业在现代化发展中,林业技术得以推广,其作为当前的重点内容。促进林业的积极发展,能维护生态平衡性,也能实现人与自然的和谐进步。但是,在新时期发展下,我国林业技术的

期刊

生态林业技术推广环境

谈现代汽车的金属腐蚀与防腐措施

汽车在制造和使用过程中，不可避免地要因各种因素的影响而产生金属腐蚀，从而影响汽车的正常使用。本文介绍了腐蚀基本原理、汽车用材的耐蚀性；分析了影响汽车腐蚀的环境因素；提出

期刊

现代汽车金属腐蚀防腐措施the modem automobile metals decays the antisepsis measure

柑橘病虫害防治问题探讨

柑橘种植与多种因素相关,包括日照、湿度、土壤、地形、海拔、风向等。一般情况下,温度控制在12℃至37℃内为宜,保证其优质丰产则需要充足的日照时间（1500—2000小时）,柑橘最适

期刊

柑橘病虫害防治

PMDA：一种物理模型驱动的物联网软件体系结构

实现众多物理应用之间的互联是建立物联网的基本方法．然而，如何设计一种有效的架构指导物理应用的水平化互联是目前物联网研究领域尚未解决的问题之一．针对该架构设计问题，提出了

期刊

物联网物理应用软件体系结构物理模型感执模型应用模型IoT physical applications software architecture p

人工影响天气在农业防灾减灾服务中的应用分析

人工影响天气是气象为农服务的重要手段。全球气候变暖使气象灾害频发,通过人工影响天气防灾减灾来降低气象灾害给农业生产带来的影响,对于农业可持续发展有着现实意义。

期刊

人工影响天气农业生产防灾减灾应用

浅析如何提高天气预报的准确率

天气预报的准确率是保证气象业务发展的重要前提,通过对极端恶劣天气的准确预报,可以有效地保证人民的生命财产安全,把经济损失降到最低。本文首先分析了影响天气预报准确率

期刊

天气预报准确率因素措施

最坏情况下X2SAT问题的上界

其他学术论文