3SAT16个变量37个子句求解2秒钟不到

姜咏江

3阶合取范式为：

(x1’+x2’+x3’) (x1+x2’+x3’) (x1’+x2+x3’) (x1+x2+x3’) (x1’+x2’+x3) (x1+x2’+x3)

(x4’+x5+x6) (x4+x5+x6) (x4’+x5’+x6’) (x4+x5’+x6) (x4’+x5’+x6) (x7+x8+x9’)

(x7+x8’+x9) (x7’+x8’+x9’) (x7+x8+x9) (x7’+x8+x9’) (x10’+x11’+x12’) (x10+x11’+x12’)

(x10’+x11+x12’) (x10+x11+x12’) (x10’+x11+x12) (x13’+x14+x15’) (x10+x11’+x12)

(x10+x11+x12) (x10’+x11+x12) (x13+x15’+x16) (x1+x7’+x9’) (x10+x11+x16’)

(x2’+x4+x12’) (x1’+x5’+x8) (x9+x13+x16’) (x3+x6+x10) (x11’+x15+x16) (x1+x8’+x12)

(x2+x3+x4) (x2+x3+x8’) (x1’+x2+x16’)

程序运行2秒，得出的解向量为：

100 101 100  110 111 0

100 101 100  010 111 0

100 101 100  000 111 0

100 101 100  000 110 0

这个结果是用我设计的软件求出的，验证一下都是解。随便改一个数码，例如，将最后一个向量的末位改成1，那么(x10+x11+x16’)值为0了。

初步成果，还在深入。转：http://blog.sciencenet.cn/blog-340399-928224.html 

2015-8-20