关于SAT问题物理模型猜想的一个反例

针对关于SAT问题物理模型的一个猜想,得到了该猜想成立的必要条件.然后构造出反例,说明该猜想是不成立的.同时指出,考虑到"算法吸引区"的存在,这并不降低应用该物理模型求解SAT问题的良好的现实效果.     

一个SAT问题有解的充要条件

合取范式可满足性问题(简称SAT问题)是一个NP完全问题.引入了一个饱和合取范式的概念,利用饱和合取范式的性质,对SAT问题的本质进行了研究.在此基础上,证明了一个SAT问题有解的充要条件,它为SAT问题完全算法和非完全快速算法的深入研究提供了一条新的思路.     

基于离散Lagrange方法的分布式SAT问题求解

基于对离散Lagrange方法(DLM)的扩充，提出一个分布式SAT求解算法：EDLMSAT。求解过程中，单个Agent的行为由预先定义的EDLM规则所决定，这些局部的行为聚集起来，形成整个系统对问题的求解趋势。设计了一些对3-SAT基准问题的模拟实验，实验结果表明了这个算法良好的求解性能。     

关于H.Silverman猜想的反例

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}内为星像。本文指出该猜想不成立。     

一个素数猜想的反例

对于正整数n,设pn是第n个素数。本文证明了:不等式穴n 1雪pn-npn 1<12穴n 1雪950对于某些正整数n不成立。     

一种求解难SAT问题的改进DP算法

DP算法是求解SAT问题的最有效完全算法之一，论文分析和讨论了DP算法中的各种分枝文字策略，并基于对不满足解数估计的方法，提出了一个有效的分枝文字策略，实验结果表明，提出的改进DP算法对难SAT实例有较好的平均性能。     

关于Makowski-Schinzel的一个猜想

设ψ(n),σ(n)分别是正整数n的Euler函数与约数和函数.证明了,如果n存在素因子p,使p2| n,则ψ(σ(n))/n＞-1/2,从而完全解决了Makowski-Schinzel的一个猜想.     

一次性求解多个SAT问题

在实际应用中通常需要求解对应CNF(Conjunctive Normal Form)公式之间仅相差几个子句的一系列SAT(Satisfiability Problem)问题,但目前绝大多数SAT求解算法都是针对单一SAT问题设计的。为此,基于DPLL提出了nDPLL算法,并在随机问题上对该算法的效率进行测试。实验结果表明,nDPLL算法能一次性求解多个SAT问题,对于特定范围的CNF公式集具有较高的效率,CNF公式集的规模越大、相近因子越高、子句数和变量数的比值越大,则nDPLL算法的效率越高。     

关于合取范式可满足性问题的复杂性分析

合取范式可满足性问题(简称SAT问题)是典型的NP完全问题,本文引入了一个饱和子句集的新概念,利用饱和子句集的特性,研究了SAT问题的复杂性,证明了SAT问题复杂性为多项式的一个充分条件,并揭示了二元可满足性问题与三元可满足性问题的本质差别。因此,通过变换来提炼出SAT问题的复杂性的本质特征,并加以研究的方法,是SAT问题的复杂性研究的一种有效方法。     

关于Catlin—猜想的反例

Catlin的2／3－猜想：若G是超欧拉图，G≠K1，那么G有一个欧拉生成子图H，使得|E(H)|≥2／3|E(G)|。给出了Catlin的2／3－猜想的一些反例。     

关于素数的一个猜想

对于正整数n，设pn是第n个素数。本文证明了：不等式（√pn-logpn＋1）/（√pn＋1＋logpn）≥（√3-log5）/（√5-log3）对于任何正整数n都成立。     

关于Yorke的一个猜想

本文证明了由Ｙｏｒｋｅ等人提出的猜想是成立的。同时本文给出反例，说明ＪｕＲａｎｇ Ｙａｎ关于同一问题所给的证明是错误的。     

基于SAT的分离制造攻击方法

芯片代工厂可能进行诸如IP盗版、过度生产和硬件木马插入等一系列的恶意攻击.分离制造是一种抵御来自芯片代工厂芯片攻击的重要技术.针对分离制造工艺,目前最好的攻击方法是基于网络流的邻近攻击算法,但在多数情况下,这种邻近攻击算法并不能完全恢复出原始电路.本文提出了一种基于布尔可满足性的攻击方法(SplitSAT),它利用功能正常的电路作为黑箱模型,利用多路复用器对待攻击的不完整电路建模为逻辑加密电路,将恢复电路连接关系的问题转化为逻辑解密的可满足性问题,采用已有的CycSAT算法求解带环路的可满足性问题,可显著提高邻近攻击的成功率.考虑到SAT算法可求解的问题规模有限,本文提出经验式的解空间缩减方法,利用现有物理信息和自动化布局布线工具的特点,降低了解空间规模,提高了SplitSAT攻击效率.实验结果验证了本文提出SplitSAT算法的有效性.     

关于Giuenbaum的一个猜想

证明了平面上由闭三角形的平移构成的集族，若其中任意两个集合相交，则该集族具有Ⅱ^3性质。     

利用正交方法解SAT问题

提出了一种解决SAT问题的新算法.该算法首先定义了子句之间的正交关系;然后从消除子句之间的交叠信息出发,利用正交子句的特性,结合有效的简化技术,逐渐将问题简化为一组与原问题完全等价的正交子句组;最后,根据正交子句组对整个赋值空间的覆盖情况来判断SAT是否满足.该算法为SAT问题的解决提供了一个新的思路.     

一个求解SAT问题的随机算法

本文中引入了一个求解满足性问题的随机算法。在该算法中,利用CNF公式转换为其对偶式——DNF公式,通过对满足DNF公式的真值赋值数Y作出估计。根据Y与2n比较结果,对CNF公式的可满足性进行估计并对其满足性进行判断。     

关于优美指数的一个猜想

证明了64不是优美指数．这一结果否定了有关优美指数的一个猜想．     

关于Minkowski猜想的一个结果

本文证明了Minkowski猜想对于n阶有理数矩阵是成立的。     

关于Fibonacci多边形的一个猜想

Filronacci数有许多美妙的性质，与Fibonacci数有关的一些问题也往往引人入胜[1][2][3]．本文书给出Fibonacci多边形的定义，并在此定义下证明Fibonacci多边形的一种特殊性质，最后提出关于Fibonacci多边形的一个猜想以及与其有关的若干问题。