博文
计算机科学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 |
电话：13651184072，13522984778
2018年1月19日
https://blog.sciencenet.cn/blog-340399-1095882.html
上一篇：有感《第六名：“基因剪刀”改造出三眼蚊子》
下一篇：P与NP问题的认知盲点
