【摘 要】
：
布尔可满足性问题(SAT)是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句
【基金项目】
：
国家自然科学基金(61271264,11471110).
论文部分内容阅读
布尔可满足性问题(SAT)是指对于给定的布尔公式,是否存在一个可满足的真值指派.这是第1个被证明的NP完全问题,一般认为不存在多项式时间算法,除非P=NP.学者们大都研究了子句长度不超过k的SAT问题(k-SAT),从全局搜索到局部搜索,给出了大量的相对有效算法,包括随机算法和确定算法.目前,最好算法的时间复杂度不超过O((2-2/k)^n),当k=3时,最好算法时间复杂度为O(1.308^n).而对于更一般的与子句长度k无关的SAT问题,很少有文献涉及.引入了一类可分离SAT问题,即3-正则可分离可满足
其他文献
应用１９９８年６～８月四川和重庆市探空资料，分析了青藏高原东侧大气边界层风场演变与长江上游暴雨和长江洪水的关系。结果表明：１９９８年夏季长江上游的暴雨天气与高原东侧成都边界层风场变化密切
随着经济的增长和人们对健康需求的提高,开展社区卫生服务已经成为医疗改革的重要内容[1]。根据＂小病在社区,大病进医院,康复回社区＂的原则,酒泉市人民医院根据本市相关政策和
<正>随着语义万维网的提出和大数据的发展,本体和知识工程再次受到学术界和业界的广泛关注.计算机领域的"本体"是指"共享概念的形式化和显示说明".本体首先面临的问题是本体
长期以来,时延估计一直是信号分析和处理的一个重要研究方向,又是目标定位跟踪系统的关键技术,在声纳、雷达、地震等领域被广泛应用。本文就基于自相关与基于LMS自适应的两种
在医疗服务过程中．除了先进的医疗技术和先进的医疗设备硬件实力之外，医院的制度化管理和人性化的服务软实力，也是医院服务水平和社会文明进步的标志。再结合我国医疗卫生事业所
对UARS卫星1992、1993、1994、1995、1996、1998年夏季的HALOE观测资料分别进行客观分析,把卫星观测资料插值到5°×5°的网格点上.并分别做了30°N和40