CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

二进制数纠缠态与SAT问题全解

已有 4153 次阅读 2017-3-1 13:16 |个人分类:SAT问题|系统分类:科研笔记| 子句标志消去法, 量子纠缠态, 数的纠缠态


姜咏江

最近读了一篇网传中国科学院院士,南方科技大学创校校长关于“量子纠缠”等方面的报告文,院士主张“人类的主观意识是客观物质世界的基础——客观世界很有可能并不存在!”真是“科学透顶”!

我研究P/NP问题的SAT问题求解,一不小心竟然整出了二进制数域的“纠缠态”,看来我也进了量子力学的空前大世界了。

纠缠态源自量子态,据说量子有01和纠缠态。纠缠态如何用数码来表示?因为是0,又是1,只要一观察就出现01状态,这叫“坍塌”。我将n位二进制数表示成n个“*”组成的字符串,用来代表02n-1那些n位二进制数,每一个*代表01,具体是0还是1,只有需要做子句标志消去法时,才能看到。你看是不是同量子一样纠缠了?

我在2015年搞过这个东西(http://blog.sciencenet.cn/blog-340399-908661.html),只是当时尚不很明确,也没想到“纠缠”这个概念。现在明白了,这是二进制限位数的纠缠态!

我们知道,n个逻辑变量构成的合取范式CNF1的可能解,应当是一个n位二进制数。在没求出CNF=1的解时,这02n-1个二进制数都可能是解。把它们全表示出来,最简单就是我上面提到的n*,亦即我现在说的纠缠态,我们不妨称之为“解纠缠”。解纠缠也可以在可以配合01数码表示数。

我的子句计数法,又叫子句标志消去法。什么叫子句标志?就是将子句用0 1表示,如果子句的数码位置和n位二进制数对应位置数码相同,那么就称这个n位二进制数是这个子句的标志,也可以叫属于这个子句的可能解。

现在我举例来说明怎么用这个“解纠缠”来表示的n位二进制数求SAT的解。1是一个逻辑电路的合取范式,可以用作电路检测(https://en.wikipedia.org/wiki/Tseytin_transformation)。这个SAT的可能解有11位,为***********,这代表了0000000000~1111111111这些数,这就是纠缠态。

让解纠缠的某一位塌缩,是通过消去子句来“观察”的。塌缩会会产生解纠缠分裂。如何分裂?

*表示01的纠缠态,如果我们用0测试,它就塌缩成了1,如果用1测试,它就塌缩成了0。如果是两个**,它可以纠缠表示00011011,用其中任何一个去测试,都会塌缩成剩余的3个。一般地,用k位二进制数测试k位解纠缠,就会塌缩出2k-1个不包含测试二进制数的k位二进制数集合。如果一个数有i位对应*0ik,那么这个解纠缠就会裂变成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,那么***********就分裂成了**********011位“坍塌”了。

x1

x2

x3

x4

x5

x6

x7

x8

x9

x10

x11

*

*

*

*

*

*

*

*

*

*

0

消去子句x1x4=11,第一和第四位置去掉1,那么**********0就分裂成了0**0******00**1******01**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******01**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******01**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

上一篇:科学研究中没有霸气成不了大器
下一篇:科研需要坚韧不拔的意志和无所畏惧的精神
收藏 IP: 1.180.212.*| 热度|

2 彭雷 rxan1234

该博文允许注册用户评论 请点击登录 评论 (5 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-12-5 14:57

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部