网友姜咏江提出“k-CNF-SAT子句消去法”，认为其算法的时间复杂度是“多项式时间”，从而一举解决了K－SAT问题。我们认为其中存在双重错误，一方面，模糊了“多项式时间”的“立场”，将多项式时间解决的“一维数组的搜索问题”（P）混淆为“K（K>=3）－SAT问题”（NP）；另一方面，将解决若干K－SAT问题实例混淆为解决K－SAT问题。所以，此“消去法”不过是演示了P＝P，并非“证明”P＝NP。

为解析此“消去法”，我们将之与普通的“穷举法”进行对比，并借用一个3变元的2SAT的实例来说明之。

一，网友姜咏江的“消去法”

用子句消去计数法求解k-CNF-SAT问题算法如下（见http://blog.sciencenet.cn/blog-340399-905817.html）：

（0）设立n元单侧计数器：x1’x2’x3’…xn-1’xn’[],x1’x2’x3’…xn-1’xn [],…, x1x2x3…xn-1xn []，共计2n个。计数器后面的方括号内放k个变量都在其中的子句数。计数器初值为0。

（1）去掉值总为1的恒一子句，则n元k-CNF的子句最多剩有。

  从前到后检查每个子句，并将k个变量都在某计数器中的计数器加1。这一过程显然是多项式时间。

（2）计数后，寻找计数器为0的计数器名称，以其每个变量表示的反码取值，得到的n位二进制数就是这个k-CNF-SAT的全部解。

（3）若没有计数器值为0，则表示此k-CNF-SAT无解。

例子：f(x1, x2, x3)=(x1v x2)(¬x2 v x3)(¬x1v x3)，求满足f(x1, x2, x3)=1的解。

3个变元x1x2x3有2^3＝8个计数器，对应3个变元的8个赋值，计数器的名称用对应的3个变元或变元的非表示：

000 x1’x2’x3’    [0]

001 x1’x2’x3    [0]

010 x1’x2x3’    [0]

011 x1’x2x3    [0]

100 x1x2’x3’    [0]

101 x1x2’x3    [0]

110 x1x2x3’    [0]

111 x1x2x3    [0]

对每个子句，并将2个变量或变元的非都在某计数器中的计数器加1：

(x1v x2)

000 x1’x2’x3’    [0]

001 x1’x2’x3    [0]

010 x1’x2x3’    [0]

011 x1’x2x3    [0]

100 x1x2’x3’    [0]

101 x1x2’x3    [0]

110 x1x2x3’    [1]

111 x1x2x3    [1]

(¬x2 v x3)

000 x1’x2’x3’    [0]

001 x1’x2’x3    [1]

010 x1’x2x3’    [0]

011 x1’x2x3    [0]

100 x1x2’x3’    [0]

101 x1x2’x3    [1]

110 x1x2x3’    [1]

111 x1x2x3    [1]

(¬x1v x3)

000 x1’x2’x3’    [0]

001 x1’x2’x3    [2]

010 x1’x2x3’    [0]

011 x1’x2x3    [1]

100 x1x2’x3’    [0]

101 x1x2’x3    [1]

110 x1x2x3’    [1]

111 x1x2x3    [1]

寻找计数器为0的计数器名称，以其每个变量表示的反码取值，得到的3位二进制数就是这个2-CNF-SAT的全部解：

－000 x1’x2’x3’[0]

计数器真值000取反111，满足f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(1)。

－010x1’x2    x3’[0]

计数器真值010取反 101，满足f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(1)。

－100x1    x2’x3’[0]

计数器真值100取反 011，满足f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(1)。

二，普通的“穷举法”

现在用普通的“穷举法”求解此实例，算法从3个变元的8个赋值出发，验证每个赋值是否能满足f：

000 x1’x2’x3’

f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(0)(1)(1)=0

001 x1’x2’x3

f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(0)(1)(1)=0

010 x1’x2x3’

f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(0)(1)=0

011 x1’x2x3

f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(1)=1

100 x1x2’x3’

f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(0)=0

101 x1x2’x3

f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(1)=1

110 x1x2x3’

f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(0)(1)=0

111 x1x2x3

f=(x1v x2)(¬x2 v x3)(¬x1v x3)=(1)(1)(1)=1

同样可以得出f的三个解：

－011 x1’x2x3

－101 x1x2’x3

－111 x1x2x3

三，解析网友姜咏江的“消去法”

由此可见，网友姜咏江的“消去法”实际上只是普通的“穷举法”，其“算法执行时间”＝c＊2^n，c是子句的个数。

可以从二个不同的角度，解读“消去法”的“算法时间复杂度”：

1，若称“消去法”的时间复杂度是“多项式时间”：O（m），m＝2^n，那么，是相对于整个真值表而言的，换句话说，问题的规模是真值表的大小。在这种情况下，此“消去法”本质是在一维数组的真值表中搜索满足某性质的元素，而“一维数组的搜索问题”不过是一个普通的P问题而已，存在着“多项式时间”算法。

2，若称“消去法”的时间复杂度是“指数时间”：O（2^n），那么，是相对于K－SAT的合取范式而言的，问题的规模是n个变元，故此“消去法”可看作是求解若干KSAT实例的算法，但算法的时间复杂度是“指数时间”，而非“多项式时间”，故不能将此算法一般化为求解K－SAT问题。

也就是说，网友姜咏江认为解决了P＝NP，不过是在演示P＝P，与真正的NP无涉。