征求数字电路优化和基因计算等方面合作者

姜咏江 2017-5-6 13:27

征求数字电路优化和基因计算等方面合作者 姜咏江 布尔电路可满足性问题，即一般称为 SAT 问题，长时间没有多项式时间的快速算法出现。 DPLL 方法虽然能够完备求出满足解，但是速度较慢，特别当合取范式 CNF=1 有唯一解的时候， DPLL 获得其可满足解，消耗的时间叫人难以忍受。 本人发明的子句消去法求 3-SAT 满 ...

个人分类: SAT问题|3298 次阅读|没有评论

科研需要坚韧不拔的意志和无所畏惧的精神

姜咏江 2017-5-1 22:20

姜咏江 有一段时间没写博文了，原因很简单，忙着将子句消去法写成计算机程序。说实在的，对一个七十多岁的人来说，还真是有点玩命。但我这个人办事不愿意半途而废。今天是“五一”劳动节，我确实还真地劳动了一番，将求 3-SAT 满足解的程序彻底完成了。高兴之余，想起来写点，以作为纪念。 为什么要拼命 ...

个人分类: 3SAT解法|4243 次阅读|没有评论

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

热度 2 姜咏江 2017-3-1 13:16

姜咏江 最近读了一篇网传中国科学院院士，南方科技大学创校校长关于“量子纠缠”等方面的报告文，院士主张“ 人类的主观意识是客观物质世界的基础 —— 客观世界很有可能并不存在！ ”真是“科学透顶”！ 我研究 P/NP 问题的 SAT 问题求解，一不小心竟然整出了二进制数域的“纠缠态”， 看来我也 ...

个人分类: SAT问题|3764 次阅读|5 个评论 热度 2

SAT求解与逻辑电路检测。

姜咏江 2017-2-22 21:15

姜咏江 逻辑电路基本上都是与、或、非门电路搭建起来的。电路运行中如何检测每个器件的好坏？实际上可以通过 SAT 表达式求出的解来进行验证。我这里举一个维基百科上的实际例子来说明这个问题的解决办法。 在 https://en.wikipedia.org/wiki/Tseytin_transformation 网页可以找到 图 1 这个逻辑电路。 ...

个人分类: SAT问题|6468 次阅读|没有评论

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问题|9018 次阅读|1 个评论 热度 1

我似乎感觉完成了一项重大任务

热度 2 姜咏江 2017-2-18 18:30

姜咏江 今天得闲，浏览了 ECCC 网站，好像是以色列主办的，过去没接触过。浏览 2017 年的文章，首先被 ScottAaronson 教授的 P ? = NP 一文所吸引。文章太长，总而言之是 P/NP 问题很难，很重要等，没见到问题已经解决的字样。 数学证明具有很强的逻辑性，但基础是概念和事实。文中提到尚未见到多项式 ...

个人分类: P/NP问题|3502 次阅读|3 个评论 热度 2

破解SAT问题必须要解决的几个层次问题

姜咏江 2017-2-6 05:52

姜咏江 逻辑变量的可满足性问题 SAT 的破解，用子句消去法求解需要解决五个层面的问题。 第一， k 阶子句块什么情况下无解？ k 阶子句块有 2 k 个不同的子句，则一定无解。例如， 3 个变量的子句块如果有 8 个不同的子句，那么合取范式 CNF=1 一定无解。改变一下判断方法：一个变量在 k 阶子句块中有 ...

个人分类: SAT问题|3777 次阅读|没有评论

中国的科学院工程院院士应该是干什么的？

热度 6 姜咏江 2017-2-3 09:16

姜咏江 中国的科学院和工程院院士德高望重，经验丰富，绝大多数都在本学科或本领域创造过辉煌的成就。不可否认，其中有些人还是本领域的创新人才，但能够真正横刀立马，冲在前面拼杀的能有多少？如果将中国现阶段的科技创新重任都放在这些人的肩上，让他们之中再现世界的大师，科学的领军人物，未免会多少影响后 ...

个人分类: 随笔|5851 次阅读|10 个评论 热度 6

到底什么是难懂的P与NP问题

热度 3 姜咏江 2017-2-1 17:43

姜咏江 美国克雷数学所悬赏百万美元的千禧难题， P 与 NP 问题是一个概念难懂的极其重要的问题。理解好这个概念，对快速解决 NP 类型问题十分有帮助。 1. 什么是问题？ 所谓问题是由三部分组成的：输入、限制条件和结果。其中限制条件是确定的，而输入和结果都是可变的，而且输入和结果都 ...

个人分类: P/NP问题|19783 次阅读|4 个评论 热度 3

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