共查询到20条相似文献,搜索用时 0 毫秒
1.
针对关于SAT问题物理模型的一个猜想,得到了该猜想成立的必要条件.然后构造出反例,说明该猜想是不成立的.同时指出,考虑到"算法吸引区"的存在,这并不降低应用该物理模型求解SAT问题的良好的现实效果. 相似文献
2.
合取范式可满足性问题(简称SAT问题)是一个NP完全问题.引入了一个饱和合取范式的概念,利用饱和合取范式的性质,对SAT问题的本质进行了研究.在此基础上,证明了一个SAT问题有解的充要条件,它为SAT问题完全算法和非完全快速算法的深入研究提供了一条新的思路. 相似文献
3.
唐屹 《中山大学学报(自然科学版)》2003,42(6):8-10,18
基于对离散Lagrange方法(DLM)的扩充,提出一个分布式SAT求解算法:EDLMSAT。求解过程中,单个Agent的行为由预先定义的EDLM规则所决定,这些局部的行为聚集起来,形成整个系统对问题的求解趋势。设计了一些对3-SAT基准问题的模拟实验,实验结果表明了这个算法良好的求解性能。 相似文献
4.
黄心中 《华侨大学学报(自然科学版)》1992,13(3):299-301
H. Silverman考虑了Szego定理的一般情形,提出下列猜想:设 f(z)是单位圆U={|z|<1}内的解析、单叶凸函数,{a■是f(z)在z=0的Talor展式的系数序列,a_0=0,a_1=1,若{a_■=0是{a_n}的任一子序列(有限或无限),则由{a_(nj)}■所组成的Talor展式在{|z|<1/4}内为凸像,在{1=1<1/2}内为星像。本文指出该猜想不成立。 相似文献
5.
一个素数猜想的反例 总被引:1,自引:0,他引:1
乐茂华 《苏州科技学院学报(自然科学版)》2004,21(2):21-22
对于正整数n,设pn是第n个素数。本文证明了:不等式穴n 1雪pn-npn 1<12穴n 1雪950对于某些正整数n不成立。 相似文献
6.
7.
DP算法是求解SAT问题的最有效完全算法之一,论文分析和讨论了DP算法中的各种分枝文字策略,并基于对不满足解数估计的方法,提出了一个有效的分枝文字策略,实验结果表明,提出的改进DP算法对难SAT实例有较好的平均性能。 相似文献
8.
杨仕椿 《北华大学学报(自然科学版)》2004,5(2):106-107
设ψ(n),σ(n)分别是正整数n的Euler函数与约数和函数.证明了,如果n存在素因子p,使p2| n,则ψ(σ(n))/n>-1/2,从而完全解决了Makowski-Schinzel的一个猜想. 相似文献
9.
在实际应用中通常需要求解对应CNF(Conjunctive Normal Form)公式之间仅相差几个子句的一系列SAT(Satisfiability Problem)问题,但目前绝大多数SAT求解算法都是针对单一SAT问题设计的。为此,基于DPLL提出了nDPLL算法,并在随机问题上对该算法的效率进行测试。实验结果表明,nDPLL算法能一次性求解多个SAT问题,对于特定范围的CNF公式集具有较高的效率,CNF公式集的规模越大、相近因子越高、子句数和变量数的比值越大,则nDPLL算法的效率越高。 相似文献
10.
合取范式可满足性问题(简称SAT问题)是典型的NP完全问题,本文引入了一个饱和子句集的新概念,利用饱和子句集的特性,研究了SAT问题的复杂性,证明了SAT问题复杂性为多项式的一个充分条件,并揭示了二元可满足性问题与三元可满足性问题的本质差别。因此,通过变换来提炼出SAT问题的复杂性的本质特征,并加以研究的方法,是SAT问题的复杂性研究的一种有效方法。 相似文献
11.
李登信 《渝州大学学报(自然科学版)》2002,19(1):1-2
Catlin的2/3-猜想:若G是超欧拉图,G≠K1,那么G有一个欧拉生成子图H,使得|E(H)|≥2/3|E(G)|。给出了Catlin的2/3-猜想的一些反例。 相似文献
12.
乐茂华 《邵阳学院学报(自然科学版)》2005,2(3):1-1
对于正整数n,设pn是第n个素数。本文证明了:不等式(√pn-logpn+1)/(√pn+1+logpn)≥(√3-log5)/(√5-log3)对于任何正整数n都成立。 相似文献
13.
14.
芯片代工厂可能进行诸如IP盗版、过度生产和硬件木马插入等一系列的恶意攻击.分离制造是一种抵御来自芯片代工厂芯片攻击的重要技术.针对分离制造工艺,目前最好的攻击方法是基于网络流的邻近攻击算法,但在多数情况下,这种邻近攻击算法并不能完全恢复出原始电路.本文提出了一种基于布尔可满足性的攻击方法(SplitSAT),它利用功能正常的电路作为黑箱模型,利用多路复用器对待攻击的不完整电路建模为逻辑加密电路,将恢复电路连接关系的问题转化为逻辑解密的可满足性问题,采用已有的CycSAT算法求解带环路的可满足性问题,可显著提高邻近攻击的成功率.考虑到SAT算法可求解的问题规模有限,本文提出经验式的解空间缩减方法,利用现有物理信息和自动化布局布线工具的特点,降低了解空间规模,提高了SplitSAT攻击效率.实验结果验证了本文提出SplitSAT算法的有效性. 相似文献
15.
16.
利用正交方法解SAT问题 总被引:1,自引:0,他引:1
提出了一种解决SAT问题的新算法.该算法首先定义了子句之间的正交关系;然后从消除子句之间的交叠信息出发,利用正交子句的特性,结合有效的简化技术,逐渐将问题简化为一组与原问题完全等价的正交子句组;最后,根据正交子句组对整个赋值空间的覆盖情况来判断SAT是否满足.该算法为SAT问题的解决提供了一个新的思路. 相似文献
17.
本文中引入了一个求解满足性问题的随机算法。在该算法中,利用CNF公式转换为其对偶式——DNF公式,通过对满足DNF公式的真值赋值数Y作出估计。根据Y与2n比较结果,对CNF公式的可满足性进行估计并对其满足性进行判断。 相似文献
18.
19.
20.
Filronacci数有许多美妙的性质,与Fibonacci数有关的一些问题也往往引人入胜[1][2][3].本文书给出Fibonacci多边形的定义,并在此定义下证明Fibonacci多边形的一种特殊性质,最后提出关于Fibonacci多边形的一个猜想以及与其有关的若干问题。 相似文献