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

博文

计算机科学P/NP问题并行计算处理器研制成功!

已有 4007 次阅读 2018-1-20 12:38 |个人分类:P/NP问题|系统分类:科研笔记| 并行处理器

纯离散数据并行处理运算器计算机征询合作者

姜咏江

   现在的计算机处理器,本质上是一种顺序处理方式的产物。这种计算机处理连续数据的问题非常有效,但处理象哈密顿回路、超大规模集成电路可靠性、密码破译、人工智能、基因准确计算等一系列纯离散数据类型的问题时,计算的时间复杂度都是指数型的,超长的耗时是难以忍受的。处理这类超长时间才能解决的问题,人们自然想到多处理器并行,于是搞起超级多处理器计算机,借助于网络,搞多处理机协同操作。但从效率,投入、易用等诸多方面来看,都有些不尽人意。这就迫切需要研发轻便、易用、类似个人计算机规模,既能够处理连续数据,也能够并行处理纯离散型数据,功能超快超强的计算机。

   如果您了解计算机科学的最大难题——P Versus NP problem,您就一定知道,构造一种能够快速处理SAT问题的处理器是何等的重要。2015年,在理论上我找到了完成求SAT问题全解的“子句标志消去法”(已在科学网博客中发表,简介请见后面介绍)。该方法是不是多项式时间算法,关键取决于计算机能否在2n个可能解中,在一个计算机节拍,就能消去所有包含这个子句的那些可能解。

   理论的成功,并不能给企业带来更大的收益,而技术的创新,会为企业带来源源不断的财富。这不论对硬件还是软件的公司来说,历史已经证明都是对的。为了不使理论落空,也为了国家和个人计算机事业的发展。经过了几十年的艰苦研究,终于制造成功了SAT运算器。SAT运算器会使那些用现在的计算机要算上百年、千年的问题,有望在极短的时间内获得解决。SAT处理器存在的计算机一定是当今世界最先进的计算机系统。SAT问题最直接的应用就是数字集成电路可靠性检测,密码破解,基因计算,求解哈密顿回路,人工智能等方面。在数字智能芯片应用如此广泛的时代,特别在航天、军事领域,杜绝器件不可靠性该是何等的重要。

   本公司已经完成了带有SAT处理器及其指令系统的验证计算机制造,下一步要在三年时间内完成这种世界上最先进的计算机系统制造。目前正在征求确有实力计算机制造企业合作,也愿意接受国内投资人参与。详细问题可面谈商定。

附录:子句标志消去法简介

数字集成电路的各点电压可靠性检测,可以通过The Tseytin transformation 转化成SAT问题求解。如何求得SAT的全部解?我这里给出一个3-SAT的例子(文字用0、1表示),只要读者将右面的n位数中含有左面子句的数码且位置相同数同子句一起逐一消去(n位数没有时,只消去子句)。当所有子句消去之后,剩下的n位数的反码都是解!这里n=5,有底纹的部分表示消去了。

可以将得到的那些n位数(左面下面的3个5位二进制数)带入上面SAT进行验证,可知完全正确。

 K个文字的子句最多有2的k次方乘以n取k的组合数,即为2kCkn,这是关于n的k次多项式。也就是说该算法时间复杂度为O(nk)。需要说明,右面的n位二进制数是装在每一个熟悉二进制表数人的心中的,正如我们熟悉十进制数的数码在什么位置一样。莫把右面的2n个数看成算法操作的一部分。这正如同x是2n以内的正整数一样,我们需要将其全部值写出来吗?

1  3-SAT和解标志

x4

x3

x2

x1

x0

 

NO

 

x4

x3

x2

x1

x0

0

0

0

 

 

 

0

 

0

0

0

0

0

1

0

0

 

 

 

1

 

0

0

0

0

1

1

0

1

 

 

 

2

 

0

0

0

1

0

1

1

1

 

 

 

3

 

0

0

0

1

1

0

 

0

1

 

 

4

 

0

0

1

0

0

1

 

1

0

 

 

5

 

0

0

1

0

1

1

1

 

 

1

 

6

 

0

0

1

1

0

0

0

 

 

0

 

7

 

0

0

1

1

1

 

1

0

1

 

 

8

 

0

1

0

0

0

 

1

1

0

 

 

9

 

0

1

0

0

1

 

0

1

1

 

 

10

 

0

1

0

1

0

 

1

1

1

 

 

11

 

0

1

0

1

1

 

0

0

0

 

 

12

 

0

1

1

0

0

 

 

0

1

0

 

13

 

0

1

1

0

1

 

 

1

0

0

 

14

 

0

1

1

1

0

 

 

1

1

0

 

15

 

0

1

1

1

1

 

 

0

0

1

 

16

 

1

0

0

0

0

 

 

 

 

 

 

17

 

1

0

0

0

1

 

 

 

 

 

 

18

 

1

0

0

1

0

1

1

0

1

0

 

19

 

1

0

0

1

1

1

0

1

1

1

 

20

 

1

0

1

0

0

0

0

1

1

1

 

21

 

1

0

1

0

1

 

 

 

 

 

 

22

 

1

0

1

1

0

 

 

 

 

 

 

23

 

1

0

1

1

1

 

 

 

 

 

 

24

 

1

1

0

0

0

 

 

 

 

 

 

25

 

1

1

0

0

1

 

 

 

 

 

 

26

 

1

1

0

1

0

 

 

 

 

 

 

27

 

1

1

0

1

1

 

 

 

 

 

 

28

 

1

1

1

0

0

 

 

 

 

 

 

29

 

1

1

1

0

1

 

 

 

 

 

 

30

 

1

1

1

1

0

 

 

 

 

 

 

31

 

1

1

1

1

1


电话:1365118407213522984778

2018119




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

上一篇:有感《第六名:“基因剪刀”改造出三眼蚊子》
下一篇:P与NP问题的认知盲点
收藏 IP: 218.60.71.*| 热度|

1 liudazhe

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

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

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

GMT+8, 2024-3-29 13:59

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部