目录

一，NP的形式化定义

二，集合与判断

三，人的判断

四，算法的判断

五，分析NP形式定义

六，质疑NP

NP的形式定义是用集合表达的，为了进一步理解NP，让我们回到对“集合”这个基本概念的理解上。

一，NP的形式化定义

NP存在二个被认为等价的定义：

- Definition 1 : NP is the class of problems decidable by NDTM (NonDeterminisitic Turing Machine) in polynomial time. 

- Definition 2 : NP is the class of problems verifiable by TM (Turing Machine) in polynomial time.

为了深入讨论，需要给出相应形式化定义。NP的形式化定义是借助于称之为“language（语言）”的概念，将NP与集合联系，然后从“decision problem（判定问题）”的角度定义NP。

这是NP的形式化定义版本是Timothy Y. Chow采用Papadimitriou的书“计算复杂性”的第9章所得：

- 令R为二进制字符串上的关系； 即，让R为一组有序对（x，y）的集合，其中x和y是二进制字符串。 如果存在确定性图灵机在多项式时间内判定给定的（x，y）是否在R中，我们则说R是“多项式可判定”。如果 k >= 1， 使得对于R中的所有（x，y），y的长度（我们写为| y |）最大为| x | ^ k，则R是“多项式平衡”。

- 现在我们准备定义NP。 当且仅当存在多项式可判定且多项式平衡的关系R，使得L = {x : (x,y)在R中存在y}时，就说语言L在NP中。

二，集合与判断

集合一般性指具有某种性质G(x)的对象的聚集整体，记A = {x ：G(x)}，G(x)表达元素与集合的所属关系，即任给一个x，G(x)=1，则x在A中；G(x)=0，则x不在A中。

比如：偶数的集合，集合A = {x : mod(x, 2)=0}。给定整数20，mod(20, 2)=0，故在A中；给定整数15，mod(15, 2)/=0，故不在A中。

可以说，集合的定义是基于对所属关系G(x)的“判断”，一个集合的定义有效性取决于对G(x)的“判断”。“判断”涉及判断的主体和客体。判断的客体指论域中的对象，比如：A = {x : mod(x, 2)=0}，论域是所有的整数；判断的主体一般情况下指“人”。

Georg Cantor在最初给出的集合定义中明确表达了“人”是集合定义中判断的主体：

- 集合是“我们感知或思想的”不同的对象的聚集，这些对象称为集合的元素。

- A set is a gathering together into a whole of definite, distincts objects of our perception [Anschauung] or of our thought  - which are called elements of the set.

遗憾的是，在后来流行的集合定义中将“我们感知或思想的”省略了。当人借助“机器”来判断时，判断的“主体”就是“算法”，计算机理论中的P和NP的定义正是这种情况。

三，集合与人的判断

一般情况下，一个集合的定义表达了人对某一事物确定性，在此情况下没有问题。但是，并不能保证任何一个看似成立的集合定义没有问题，比如罗素悖论：A={x∣x∉x}，因对于A本身是否属于A的判断出现矛盾，故A的定义成为问题，由此引发第三次数学危机，直到提出公理集合论才暂时解决。

四，集合与算法的判断

在计算机理论中，集合的所属关系的判断借助与“算法”，如图灵所说：

- 一般过程（算法，图灵机）判定一个给定的整数n是否有性质G(n)［比如，G（n）可能表示’n是可满足的’’或’n是一个可证明公式Godel的表达］

这样的定义首先就涉及到算法的存在性，这就是Entscheidungsproblem所讨论的核心问题。对此，图灵1936年的文章给出否定性的回答，“判定问题不可判定”：

- 。。。，I propose, therefore, to show that there can be no general process for determining whether a given formula A of the functional calculus K is provable, i.e. that there can be no machine which, supplied with any one A of these formulae, will eventually say whether A is provable.

所以，Entscheidungsproblem不是处理TM无法判定的语言，而是处理判定语言的TM的存在性。

五，NP与算法的判断

NP形式定义中涉及的集合R与L，以SAT问题为例再来分析：

- R = {(x,y) ： x is a satisfiable SAT instance and y is a satisfying assignment}

- L = {x : (x,y) is in R for some y}

也就是说，R表达令一个SAT实例满足的所有赋值的集合；L表达所有可满足的SAT实例的集合。在认知上，R与L的判定对应二个层次不同的问题。

比如：

- 实例f1 = (x1 ∨x2 ∨x3)∧(x1 ∨x2 ∨¬x3)∧(¬x1 ∨¬x2 ∨  x3) ∧ (¬x1 ∨ x2 ∨ x3), f1是 satisfiable，有四个解：x1 =0, x2=1, x3=1; x1 =0, x2=0, x3=1; x1 =1, x2=1, x3=1; x1 =1, x2=0, x3=1，故R = {(f,(0 1 1)), (f,(0 1 0)), (f,(1 1 1)), (f,(1 0 1))}。

- 实例f2= x1 ∧¬x1, f2是 unsatisfiable，无解， 故R为空集。

- L = {f1, …}，f1在L中，但f2不在L中。

如此，R和L集合的所属关系的判断就转移给“算法”了。

问：

1. R是可判定的吗？

答：Yes，R是可判定的，因为存在多项式时间算法判定R的所属关系。

2. L是可判定的吗？

答：Yes，L是可判定的，因为存在指数时间的“穷举法”判定判断L的所属关系。

六，质疑NP

然而，我们质疑NP形式定义，即“L是可判定的”流行观点。

“穷举法”，即“指数时间算法”，基于“枚举”和“验证”，集合R的生成就是“穷举法”的结果。然而，“枚举”是SAT解空间本身可枚举的性质，所以“穷举法”的本质就是“验证”，即“多项式时间验证的算法”。

既然如此，从集合所属关系判断的角度，“L是可判定的”就说明，L的判定与R的判定本质是一致的，换句话说，R与L等价。此观点同时表达NP的形式定义和NP的非形式定义中。 

于是，在理论上，NP的定义暗含P=NP；然而在实践上，无论是直觉的认知还是具体问题的求解，P与NP是二个完全不同的问题，P/=NP。于是，理论与实践产生了矛盾！

所以，我们认为，需要重新审视NP的定义，从认知与逻辑的角度入手，追本溯源到图灵关于解决Entscheidungsproblem的工作，重新审视NP与Entscheidungsproblem的关系。或许这才是解决P vs NP的根本路径，。。。

注：感谢与Timothy Y. Chow建设性的对话！