问题求解与验证的区别，答柳渝之质疑

姜咏江

对于我提出的“子句消去计数法”是多项式时间算法，柳渝网友提出了质疑（见2），她认为一个子句去检索2ⁿ个名称，对n来说一定是指数时间的。其实n是否是解决问题过程重复的决定性因素，是判断n是否是“规模”的关键。在子句变量含在哪些一侧计数器名称检索中，规模不是n而是一个取值0至2ⁿ -1的变量，理解了这一点，才能清楚子句消去计数法的“多项式时间复杂度”的本质。

不瞒各位网友，我已经用子句消去计数法设计了3-CNF-SAT运算器，只要你输入3-CNF，那么立即就会得到使3-CNF-SAT成立的全部解。

1.              问题求解与验证的区别

求解的方法（解题）是指根据给出完整的条件，通过计算一定能够得出结果，其特点是一次性成功。验证则是依据给出的条件（这个条件可能是求解的结果证书或部分条件），通过计算却不一定会得出正确结果，其特点是一个正确结果的确定，需要不确定性的多次验证。

例如，在2ⁿ个n位二进制数的集合中查找某个值不超过2ⁿ-1的数，问，这是一个验证过程，还是求解过程？

显然，这是一个求解过程，因为你总可以一次性地查询找到这个数。

求解的过程是确定性过程，即是函数。如果某过程的结果是不确定的，需要判断，这就是验证的问题了。

例如，从A地到B地走路多长时间可以到达？

这个问题看似很简单，但却是个验证问题。因为不同的人或者同一个人行走的速度会不同，因而全程消耗的时间也会不同，自然结果各不相同。对于一个人来说，他说要多少时间不能算数，到底用多长时间需要检验，或者验证，其结果往往是不确定的。验证那个人所说的时间，常需要多次检验。

回到如果查询逻辑变量的子句x_i’+x_j+x_k是否在某一个一侧计数器的名称中的问题。因为一侧名称计数器共有2ⁿ个，因而变量名称完全的。所以一次性就能够确定这个子句都能够在那几个计数器名称之中，所以这是解题的过程，而不是验证的过程。

2.              柳渝质疑与回复

[4]柳渝  2015-7-16 20:09

姜老师，您的算法“k-CNF-SAT子句消去计数法求解”的第二步：
－从前到后检查每个子句，并将k个变量都在某计数器中的计数器加1。这一过程显然是多项式时间。

对每个含k个变量的子句，您是在指数个数2^n的计数器中检查此k个变量是否出现，然后来计数的，所以这一过程是“指数时间”，而不是您说的“多项式时间”。

博主回复(2015-7-16 20:38)：不论多少个有限元素，检索的过程总是所谓多项式时间。

博主回复(2015-7-16 20:26)：因为2^n个计数器是一个数而已，在算法执行中并不发生变化。不应该将数2^n和处理操作的这种数值关系混淆。我说过，任何数都可以表成指数形式，也可以表成底数形式，故而以是否是底数形式做时间判断，恐怕是多有不妥。
本文方法就可以在所谓的多项式时间解题，即一次性求出结果。验证或判断的特点是非一次性的。试试我的方法，你可以一次求出3-CNF-sat的全部解。

[5]柳渝  2015-7-17 01:48

您说：“不论多少个有限元素，检索的过程总是所谓多项式时间。”此话需要辨析：
当我们谈论计算时间时，是有参照对象的。您的算法若相对实例的整个搜索空间（2^n），可以说是“多项式时间”，但是若相对实例的规模（n），就是“指数时间”了。

博主回复(2015-7-17 05:44)：同意你的认识。检索不需要重复，只要找到就可以，并不涉及规模。

请参考：http://blog.sciencenet.cn/blog-340399-905817.html 

2015-7-19