科学网

 找回密码
  注册
搜索
热搜: 科学 论文
搜索
征求数字电路优化和基因计算等方面合作者
姜咏江 2017-5-6 13:27
征求数字电路优化和基因计算等方面合作者 姜咏江 布尔电路可满足性问题,即一般称为 SAT 问题,长时间没有多项式时间的快速算法出现。 DPLL 方法虽然能够完备求出满足解,但是速度较慢,特别当合取范式 CNF=1 有唯一解的时候, DPLL 获得其可满足解,消耗的时间叫人难以忍受。 本人发明的子句消去法求 3-SAT 满 ...
个人分类: SAT问题|2479 次阅读|没有评论
科研需要坚韧不拔的意志和无所畏惧的精神
姜咏江 2017-5-1 22:20
姜咏江 有一段时间没写博文了,原因很简单,忙着将子句消去法写成计算机程序。说实在的,对一个七十多岁的人来说,还真是有点玩命。但我这个人办事不愿意半途而废。今天是“五一”劳动节,我确实还真地劳动了一番,将求 3-SAT 满足解的程序彻底完成了。高兴之余,想起来写点,以作为纪念。 为什么要拼命 ...
个人分类: 3SAT解法|2802 次阅读|没有评论
二进制数纠缠态与SAT问题全解
热度 2 姜咏江 2017-3-1 13:16
姜咏江 最近读了一篇网传中国科学院院士,南方科技大学创校校长关于“量子纠缠”等方面的报告文,院士主张“ 人类的主观意识是客观物质世界的基础 —— 客观世界很有可能并不存在! ”真是“科学透顶”! 我研究 P/NP 问题的 SAT 问题求解,一不小心竟然整出了二进制数域的“纠缠态”, 看来我也 ...
个人分类: SAT问题|2808 次阅读|5 个评论 热度 2
科学研究中没有霸气成不了大器
热度 10 姜咏江 2017-2-27 11:40
科学研究没有霸气,自然成不了大器。何谓霸气?即敢研究别人研究不了的问题,敢去解决别人长期未能解决的问题。这一点外国人似乎比我们中国人勇敢,值得我们学习。 生活中难以解决的问题很多,特别是那些所谓世界级的公开难题,你敢不敢去解决?勇敢地面对那些世界上还没有解决的问题,敢于探讨,钻研,有强烈的 ...
个人分类: 随笔|3440 次阅读|18 个评论 热度 10
请教编辑:为什么博文上传的插图不能进入博文?
热度 2 姜咏江 2017-2-22 21:28
如题,最近一直无法将插图嵌入,只好用图片插入。不知能否不丢图,还能象以前那样插入?
个人分类: 随笔|2391 次阅读|3 个评论 热度 2
SAT求解与逻辑电路检测。
姜咏江 2017-2-22 21:15
姜咏江 逻辑电路基本上都是与、或、非门电路搭建起来的。电路运行中如何检测每个器件的好坏?实际上可以通过 SAT 表达式求出的解来进行验证。我这里举一个维基百科上的实际例子来说明这个问题的解决办法。 在 https://en.wikipedia.org/wiki/Tseytin_transformation 网页可以找到 图 1 这个逻辑电路。 ...
个人分类: SAT问题|3755 次阅读|没有评论
P与NP问题图示解释
热度 1 姜咏江 2017-2-20 09:44
姜咏江 为了理解好P与NP问题,特作图解释。 1. P 、 NP 、 NP-complete 和 NP-hard 之间的关系图 下面 Fig.1 是国外网站见到的 P 、 NP 、 NP-complete 和 NP-hard 之间的关系图。因为没有归约表示,因而较难理解。 Fig. 1 Diagram for P ...
个人分类: P/NP问题|5860 次阅读|1 个评论 热度 1
我似乎感觉完成了一项重大任务
热度 2 姜咏江 2017-2-18 18:30
姜咏江 今天得闲,浏览了 ECCC 网站,好像是以色列主办的,过去没接触过。浏览 2017 年的文章,首先被 ScottAaronson 教授的 P ? = NP 一文所吸引。文章太长,总而言之是 P/NP 问题很难,很重要等,没见到问题已经解决的字样。 数学证明具有很强的逻辑性,但基础是概念和事实。文中提到尚未见到多项式 ...
个人分类: P/NP问题|2594 次阅读|3 个评论 热度 2
破解SAT问题必须要解决的几个层次问题
姜咏江 2017-2-6 05:52
姜咏江 逻辑变量的可满足性问题 SAT 的破解,用子句消去法求解需要解决五个层面的问题。 第一, k 阶子句块什么情况下无解? k 阶子句块有 2 k 个不同的子句,则一定无解。例如, 3 个变量的子句块如果有 8 个不同的子句,那么合取范式 CNF=1 一定无解。改变一下判断方法:一个变量在 k 阶子句块中有 ...
个人分类: SAT问题|2907 次阅读|没有评论

本页有 1 篇博文因作者的隐私设置或未通过审核而隐藏

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

GMT+8, 2020-11-30 01:28

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部