完备计算机

姜咏江

世界的事物处理过程无非两种方式。一是顺序处理方式，二是并行处理方式。电子计算机用二进制处理事物，自然也要模拟这两种方式。直至目前为止，人们使用的计算机运算器还只能模拟具有先后顺序的处理方式。对于并行的过程，计算机需要转化成顺序处理方式才能够实现。将并行的过程转化成顺序过程来处理，在时间上消耗增加是必然的代价。这样对那些数据量大一些的可并行处理的问题（例如密码破解、集成电路可靠性检测（SAT）、哈密顿回路等），基本上还束手无策。

不能够实现并行处理数据的计算机结构，体现了计算机设计的不够完备性。大量的并行处理问题，成为了计算机科学的最大难题。这些问题的有效短时间处理，是计算机设计理论和方法的最大挑战。

能够具有顺序和并行两种处理器的计算机无疑应该是完备的计算机。带有SPU处理器的计算机就是一款完备计算机。

SPU处理器是并行计算求出SAT问题满足解的处理器，它毫无疑问使当今的计算机进入了完备计算机时代。该计算机处理器采用存储计算模式，能够在多项式时间计算出SAT问题满足解。其原理，发明人几年前把它叫做“子句标志消去法”，现在看，叫“包含子句消去法”更为恰当。

下面是作者2016年写的设计并行处理器SPU的原理。现在作者已经将包含SPU设计的完备计算机带进了课堂。经过一年多的验证检验，提供给学生们的验证计算机使他们欢心鼓舞，未来的发展会让他们无可限量。

K-SAT FLAG AND ANSWER

姜咏江，中国北京100013

摘  要 用k-SAT标志消去法能轻而易举地能够求出全部解。

关键词 k-SAT,子句消去法，子句标志消去法

如果你熟悉用二进制表示数，那么k-SAT标志消去法的求解就很容易理解了。

1.         子句消去法

用二进制数表示的k-SAT，如果将一个变量的值设定为0或1，那么所有含有该变量具有相同值的子句都可以消去，然后对剩余部分继续这样求解，直至全部的变量值都设定完为止。如果这一过程的最后没有剩余子句了，那么所设的变量值全体就是这个k-SAT的满足解，否则k-SAT没有满足解。

什么情况下会有剩余子句不能消去？假如有子句x_ix_jx_k，如果这3个变量的值都设定了，并且3-SAT中有子句x_i’x_j’x_k’ （这里的“’”表示求反运算），那么这个子句肯定会剩下。x_ix_jx_k与x_i’x_j’x_k’称为互反子句。

互反子句有一个特性：没有反子句的子句变量值是满足解的组成部分。

n个变量的k-SAT最多有对互反子句。如果每个变量的值都必须设定，那么有互反子句存在的那些变量，不论怎样设定值都会有剩余子句存在，因而k-SAT也不会有满足解。

当设定一组n个变量值时，刚好k-SAT中没有这组值中组成的子句的反子句，那么就不会有剩余子句。于是n个变量的这组值就是k-SAT的满足解。

我们的问题是怎样找到这组值？

2.         解标志

二进制数表示的子句如果是一个n位数的对应组成部分，称这个子句在这个n位数中。二进制数表示的互反子句一定在不同的n位数中。若包含互反子句的n位二进制数存在，则这些n位二进制数就不会是k-SAT的满足解，而k-SAT中没有反子句的子句，一定是某个满足解的组成部分。我们可以将k-SAT的每个子句能够构成的n位二进制数找出来。如果有一个n位二进制数不包含任何k-SAT的子句，说明这个在k-SAT中没有这些子句的反子句。于是就可以用这个位二进制数能够组成的子句的反子句值做为满足解。

n元变量的k-SAT能够表明相关子句的n位数叫解标志。任何一个k-SAT的子句在解标志中，解标志为1，否则为0。

3.         求出K-SAT的全部解

用二进制数码来表示k-SAT的格式如表1左面所示，其中每个子句单独占一行。如果逻辑变量有n个，那么k-SAT的解标志就有2ⁿ个，用二进制数码表示，就如同表1右面所示的那样2ⁿ个n位二进制数。

表1  3-SAT和解标志

求k-SAT 的解过程十分简单。只要将包含子句的标志删除，那么全部子句处理完成，剩余的解标志为0的那些n位二进制数的反码，就是k-SAT的满足解。

4.         结论

k-SAT标志消去法是一个多项式时间复杂度的算法。n个变量的k-SAT最多有2^kC_n^k个子句。因为每个子句只进行一次消去解标志的操作，因而可知k-SAT求满足解的过程是一个O(n^k)时间复杂度的算法。

实际上不难看出，标志消去法是一个求k-SAT所有解的算法。

2016-6-26