基于分支回溯的NAE-3SAT问题求解算法

NAESAT问题是可满足性问题的一个重要扩展,在集合分裂、最大割集等NP完全问题中有着重要的应用.针对NAESAT问题的泛化NAE-3SAT问题,提出了一个基于分支回溯的精确算法NAE.算法给出了多种化简规则,这些化简规则很好地提高了算法的时间效率.最后证明了算法在最坏情况下的时间复杂度上界为O(1.618n),其中n为公式中的变量数目.

基于3SAT的API调用迷惑方法

现有的API调用迷惑技术通用性不强,且容易被静态分析方法识破。为此,提出一种二进制代码迷惑方法,利用3SAT非透明常量,将API调用的目标地址变换为间接地址,使分析API地址成为NP完全问题,从而无法通过静态分析获取API地址。实验结果表明,该方法增加了代码分析的难度,可使基于API调用的静态分析检测方法失效。

最坏情况下X3SAT最大海明距离问题最小上界

X3SAT最大海明距离问题是指对于一个X3SAT问题实例,寻找该问题的任意两组可满足赋值之间的最大海明距离。提出了一个基于DPLL的精确算法HMX来求解X3SAT最大海明距离问题,根据公式中某个变量在两组真值赋值中的不同取值进行分支。给出了多种化简规则,这些规则很好地提高了算法的时间效率。证明了该算法可以将X3SAT最大海明距离问题的最小上界由目前最好的O(1.7107n)缩小到O(1.6760n),其中n为公式中变量的数目。

一个可行的RSA密码破译方法

通过长年研究得到了快速高效的Hamilton路算法。利用多项式规约将3SAT问题转化为对Hamilton路的求解。尽管国际上已有过如何将3SAT问题转化为Hamilton路的方法,但那只是为了证明Hamilton路的NP完全性,因而只要求转化的结果是多项式,而不注重转化效率。为了得到将3SAT直接转化为Hamilton路的高效转化方法,以便有可能通过对后者的高效计算来实现高效计算3SAT,采取用无向图的两个节点模拟3SAT的一个变量,用13个节点的图形结构来模拟3SAT的一个子式的方法,最终实现了上述转化。该转化所需要的节点数及其边数是最优的。将大数的质因子分解转化为对3SAT的求解,从而最终通过求解Hamilton环达到破译RSA密码之目的。