3-sat剩余子句块多解表示方法 姜咏江 使用子句消去法对 3-SAT 求解,最后会碰到剩余子句块多解的情况。如果我们只选择 0 和 1 表示,就会使那些很容易就得到的多解无法表出,为此需要引进 确定了一个变量值后 的剩余多解子句块的表示方法,这样一次可以获得更多的 3SAT 解表示。下面表 1 和表 2 中的 $ 表示该变量值已经确定,上面一行是表示符号。 表 1 剩余一个子句 表示: v v t t k k q q 变量: X i X j X k X i X j X k X i X j X k X i X j X k 剩值: $ 0 0 $ 1 1 $ 1 0 $ 0 1 vv 表示 x j x k 的值是 0* 或 *0, tt 表示 x j x k 的值是 1* 或 *1, kk 表示 x j x k 的值是 1* 或 *0, qq 表示 x j x k 的值是 0* 或 *1 。“ * ”表示 0 或 1 。 表 2 剩余 2 个子句 表示: 2 2 3 3 2 2 3 3 变量: X i X j X k X i X j X k X i X j X k X i X j X k 剩值: $ 0 0 $ 1 0 $ 1 1 $ 0 1 1 1 0 1 0 0 1 0 22 表示 x j x k 的值是 01 或 10, 33 表示 x j x k 的值是 11 或 00 。 这种表示一般只用于剩余的独立子句块,如若是多解的关联段,尚需设定值求解,到最后碰到此种情况方可使用。 需要说明,子句消去法并不能够一次性求出 3SAT 的全部解,除非 3SAT 只有唯一解和只有我们这里给出的表示法能够表出的那些解。这种多解表示法只是对剩余多解子句块运用的一种表示法,目的是在 3SAT 的一次求解中能够尽可能地表示出更多的解。 剩余只有 3 种子句的子句块一定有唯一解。剩余有 4 种类型子句的子句块一定无解。 2015-12-15
Can I declare the solution to the 3SAT problem? Jiang Yongjiang Email: accsys@126.com I have been invented the Clause remove by section method that is solving the 3SAT problem. You can see the method in the following: Fig.1 The green clauses have been removed. Upper line is answer’s place. (1) and (2)no answer,but (3) has one answer. The 3-CNF=0 depends on 3 conditions: 1. 3-CNF=0,if 8 clauses in a Clause-block; 2. 3-CNF=0,if 2 variabes are fixed but other one appear 0 and 1 value in the dynamic Clause-block; 3. 3-CNF=0,if 1 variable is fixed but others appear {00,10,01,11} in the dynamic Clause-block. Besides,we will obtain the answer of 3-CNF=1. Reference: http://blog.sciencenet.cn/blog-340399-928224.html ( I'm sorry! My English is very funny.) 2015-10-19
为什么子句分段消去法可以求出 3SAT 的解? 姜咏江 A proof that P = NP could havestunning practical consequences, if the proof leads to efficient methods forsolving some of the important problems in NP . 上面这句话引自维基百科的 P versus NP 。说得是否有些过分了? 用子句分段消去法求解 3-CNF=1 的解,首先是将逻辑变量表达的问题结构化了,这种 3-CNF 特有的结构是求解的基础。子句间形成的子句块制约了子句中逻辑变量的自由变化,使 3-CNF=1 的解转化成了局部的“子句块解”和“关联段解”,从而避开了处处要从全局变量变化来确定逻辑变量值的传统方法。 子句块中子句数量的变化,为我们揭示了变量取值的规律,而关联段求解中产生的动态块,又为我们指明了段中变量值变化的规律和相互制约关系。所以我们才能够依据这些 3-CNF 中变量变化的内在规律,找到求解 3-SAT 问题满足解的方法。这是一种函数关系的体现, 不客气地说,我是计算机科学理论方法的里手,仔细研究,这个 P/NP 问题应该是纯数学的问题,它与计算机程序运行的时间计算等关系并不十分紧密,将其说成是计算机运行时间的问题不够贴切,因为计算机程序运行时间只与指令重复执行次数相关。 2015-10-16
3-SAT问题很简单,表达起来。3-SAT问题可以很难,尤其是想证明一个公式不可能满足的话。 说起来容易,做起来难啊。 希望能够用随机搜索的方法,对一个特定的3-SAT公式,找到一些该公式不可能满足的证据。如果能够对约束密度为常数的随机3-SAT公式有好的效果,那将很有趣。 2011年5月5日,赫尔辛基 终于将第一篇论文贴到arXiv上去了: “ Witness of unsatisfiability for a random 3-satisfiability formula”, Lu-Lu Wu, Hai-Jun Zhou, Mikko Alava, Erik Aurell and Pekka Orponen (arXiv:1303.2413, 2013) http://arxiv.org/abs/1303.2413 ...2013年3月11日,香港