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

博文

为什么子句分段消去法可以求出3SAT的解?

已有 2525 次阅读 2015-10-16 16:44 |个人分类:科研讨论|系统分类:科研笔记| 子句消去法, 3SAT

为什么子句分段消去法可以求出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

 




https://blog.sciencenet.cn/blog-340399-928628.html

上一篇:功底胆量自信心与成果成正比
下一篇:100个逻辑变量能够写出多少个子句?
收藏 IP: 125.39.34.*| 热度|

1 icgwang

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

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

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

GMT+8, 2024-12-26 00:07

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部