博文
二进制数纠缠态与SAT问题全解
|||
姜咏江
最近读了一篇网传中国科学院院士，南方科技大学创校校长关于“量子纠缠”等方面的报告文，院士主张“人类的主观意识是客观物质世界的基础——客观世界很有可能并不存在！”真是“科学透顶”！
我研究P/NP问题的SAT问题求解，一不小心竟然整出了二进制数域的“纠缠态”，看来我也进了量子力学的空前大世界了。
纠缠态源自量子态，据说量子有0、1和纠缠态。纠缠态如何用数码来表示？因为是0，又是1，只要一观察就出现0或1状态，这叫“坍塌”。我将n位二进制数表示成n个“*”组成的字符串，用来代表0～2n-1那些n位二进制数，每一个*代表0或1，具体是0还是1，只有需要做子句标志消去法时，才能看到。你看是不是同量子一样纠缠了？
我在2015年搞过这个东西（http://blog.sciencenet.cn/blog-340399-908661.html），只是当时尚不很明确，也没想到“纠缠”这个概念。现在明白了，这是二进制限位数的纠缠态！
我们知道，n个逻辑变量构成的合取范式CNF为1的可能解，应当是一个n位二进制数。在没求出CNF=1的解时，这0～2n-1个二进制数都可能是解。把它们全表示出来，最简单就是我上面提到的n个*，亦即我现在说的纠缠态，我们不妨称之为“解纠缠”。解纠缠也可以在可以配合0和1数码表示数。
我的子句计数法，又叫子句标志消去法。什么叫子句标志？就是将子句用0 和1表示，如果子句的数码位置和n位二进制数对应位置数码相同，那么就称这个n位二进制数是这个子句的标志，也可以叫属于这个子句的可能解。
现在我举例来说明怎么用这个“解纠缠”来表示的n位二进制数求SAT的解。表1是一个逻辑电路的合取范式，可以用作电路检测（https://en.wikipedia.org/wiki/Tseytin_transformation）。这个SAT的可能解有11位，为***********，这代表了0000000000~1111111111这些数，这就是纠缠态。
让解纠缠的某一位塌缩，是通过消去子句来“观察”的。塌缩会会产生解纠缠分裂。如何分裂？
*表示0或1的纠缠态，如果我们用0测试，它就塌缩成了1，如果用1测试，它就塌缩成了0。如果是两个**，它可以纠缠表示00，01，10，11，用其中任何一个去测试，都会塌缩成剩余的3个。一般地，用k位二进制数测试k位解纠缠，就会塌缩出2k-1个不包含测试二进制数的k位二进制数集合。如果一个数有i位对应*，0≤i≤k，那么这个解纠缠就会裂变成2i-1个。因此，我又将所谓的塌缩叫裂变。
需要说明，在论文中我将子句标志消去法叫ECPS(Elimination ofclause and Possible Solutions )，把“量子塌缩”求解的算法叫SSFA (Split Solution Form Algorithm)。
下面我们就来看看求SAT全解的例题吧。
将参考网页上的电路改变一下变量的表示，就得到了表1。
表1 一个逻辑电路的合取范式
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
| 序 |
|
|
|
|
|
|
|
|
|
| 1 |
| 1 |
1 | 1 |
|
| 2 | ||||||||
0 | 0 |
|
| 3 | ||||||||
1 | 0 |
|
| 4 | ||||||||
1 | 0 |
|
| 5 | ||||||||
1 | 1 |
|
| 6 | ||||||||
0 | 0 |
|
| 7 | ||||||||
1 | 1 |
|
| 8 | ||||||||
0 | 0 |
|
| 9 | ||||||||
1 | 0 |
|
| 21 | ||||||||
1 | 0 |
|
| 10 | ||||||||
0 | 1 |
|
| 11 | ||||||||
1 | 0 |
|
| 12 | ||||||||
0 | 1 |
|
| 15 | ||||||||
1 | 0 |
|
| 16 | ||||||||
0 |
| 1 |
| 13 | ||||||||
|
|
|
|
|
|
|
|
| 0 | 1 |
| 14 |
0 | 0 | 1 |
|
| 17 | |||||||
0 | 0 | 1 |
|
| 18 | |||||||
0 | 0 | 1 |
|
| 19 | |||||||
1 | 1 | 0 |
|
| 22 | |||||||
|
|
|
|
|
|
|
| 1 | 1 | 0 |
| 20 |
（0）初始解纠缠
表2 初始解纠缠
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
* | * | * | * | * | * | * | * | * | * | * |
消去子句x11=1，那么***********就分裂成了**********0，第11位“坍塌”了。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
* | * | * | * | * | * | * | * | * | * | 0 |
消去子句x1x4=11，第一和第四位置去掉1，那么**********0就分裂成了0**0******0，0**1******0，1**0******0。这是第一和第四位“坍塌”了。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | * | * | 0 | * | * | * | * | * | * | 0 |
0 | * | * | 1 | * | * | * | * | * | * | 0 |
1 | * | * | 0 | * | * | * | * | * | * | 0 |
消去子句x1x4=00，第一和第四位置是0，那么与0**0******0一致，消去它，剩下了0**1******0，1**0******0。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | * | * | 1 | * | * | * | * | * | * | 0 |
1 | * | * | 0 | * | * | * | * | * | * | 0 |
消去子句x1x7=10，那么与1**0******0一致，消去它，剩下了0**1******0，1**0**1***0。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | * | * | 1 | * | * | * | * | * | * | 0 |
1 | * | * | 0 | * | * | 1 | * | * | * | 0 |
消去子句x2x5=10，第2和第5位，因为对应2个星，都裂变成3个解纠缠。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 0 | * | * | * | * | * | 0 |
0 | 0 | * | 1 | 1 | * | * | * | * | * | 0 |
0 | 1 | * | 1 | 1 | * | * | * | * | * | 0 |
1 | 0 | * | 0 | 0 | * | 1 | * | * | * | 0 |
1 | 0 | * | 0 | 1 | * | 1 | * | * | * | 0 |
1 | 1 | * | 0 | 1 | * | 1 | * | * | * | 0 |
消去子句x2x6=11。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 0 | * | * | * | * | * | 0 |
0 | 0 | * | 1 | 1 | * | * | * | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | * | * | * | 0 |
1 | 0 | * | 0 | 0 | * | 1 | * | * | * | 0 |
1 | 0 | * | 0 | 1 | * | 1 | * | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | * | * | * | 0 |
消去子句x2x6=00。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 0 | 1 | * | * | * | * | 0 |
0 | 0 | * | 1 | 1 | 1 | * | * | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | * | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | * | * | * | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | * | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | * | * | * | 0 |
消去子句x2x8=11。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 0 | 1 | * | * | * | * | 0 |
0 | 0 | * | 1 | 1 | 1 | * | * | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | * | * | * | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | * | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x2x8=00。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 0 | 1 | * | 1 | * | * | 0 |
0 | 0 | * | 1 | 1 | 1 | * | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | * | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
变量x3x9在解纠缠中都是星，暂往后放，找分裂较少子句。
消去子句x4x5=10。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | * | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | * | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x5x10=01。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | * | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x6x7=10。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x9x11=01 。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x10x11=01 。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | * | 0 | * | * | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x7x10=01。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | * | * | 0 |
0 | 1 | * | 1 | 1 | 0 | 0 | 0 | * | 0 | 0 |
0 | 1 | * | 1 | 1 | 0 | 1 | 0 | * | 0 | 0 |
0 | 1 | * | 1 | 1 | 0 | 1 | 0 | * | 1 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | * | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | * | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x8x9=10。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | 1 | * | 0 |
0 | 1 | * | 1 | 1 | 0 | 0 | 0 | * | 0 | 0 |
0 | 1 | * | 1 | 1 | 0 | 1 | 0 | * | 0 | 0 |
0 | 1 | * | 1 | 1 | 0 | 1 | 0 | * | 1 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | 1 | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x1x6 x7=001。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | 1 | * | 0 |
0 | 1 | * | 1 | 1 | 0 | 0 | 0 | * | 0 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | * | 0 | 1 | 1 | 1 | 1 | 1 | * | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x2x4 x5=001。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | 1 | * | 0 |
0 | 1 | * | 1 | 1 | 0 | 0 | 0 | * | 0 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | * | 0 |
消去子句x5x7x10=110。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 0 | * | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
0 | 1 | * | 1 | 1 | 0 | 0 | 0 | * | 0 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | * | 1 | 0 |
消去子句x9x10x11=110。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 1 | * | 1 | 1 | 0 | 0 | 0 | * | 0 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | * | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
消去子句x3x9=10。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
消去子句x3x8x9=001。
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
1 | 0 | * | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
最后剩余可能解如表3所示。
表3 剩余可能解
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
表3.每行的反码数就是这个SAT问题的全部解（见表4）。
表4 SAT全部解
x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
我们知道，11个逻辑变量的SAT的全部可能解有211=2048个，如果用穷举法，得验证2048次。这里我们仅用了22次就求出全部SAT解了。这种“量子纠缠态”的方法不值得推广吗？
我相信这将带来数学和计算机科学的空前变革。数据纠缠态的计算机编程将PK量子计算机。
最后说一句，科学家要实事求是地探讨问题，瞎想会进入唯心主义的泥坑。
2017/3/1
https://blog.sciencenet.cn/blog-340399-1036854.html
上一篇：科学研究中没有霸气成不了大器
下一篇：科研需要坚韧不拔的意志和无所畏惧的精神
