“不确定性问题”（Nondeterministic Problem，NP）与“哥德尔不完全定理”

- 周剑铭，柳渝

1931年哥德尔证明：任何无矛盾的公理体系，只要包含初等算术的陈述，则必定存在一个不可判定命题，用这组公理不能判定其真假。

虽然哥德尔不完全定理只是针对包含数论的公理体系而言的，由于人们相信公理形式系统是人类知识的纯粹性与抽象性的精粹（数学和逻辑），所以哥德尔不完全定理被看成是知识和人类理性的灾难。“完全性”这个观念隐含了人类对自己的知识系统的希望或信仰，也是人类对自己的理性能力的最大期望，但这两者之间的一致性被打破了。作为纯粹形式系统自身的纯粹性质“可证性”与“完全性”与作为人类理性能力的抽象性，即作为人类理性工具的自身的能力与人类的理性能力之间的不一致性被理性工具自己完全揭露，但这种理论的深层性和思想的深刻并未被完全理解，因此哥德尔不完全定理的意义在各种不同层次和深刻性的解读上充满了分歧和论争。

哥德尔第一定理：任意一个包含一阶谓词逻辑与初等数论的形式系统，都存在一个命题，它在这个系统中既不能被证明为真，也不能被证明为否。

哥德尔第二定理：如果系统S含有初等数论，当S无矛盾时，它的无矛盾性不可能在S内证明。

哥德尔第一定理是就公理系统的自身能力而言，揭示公理系统中存在本系统无法证明的命题，就是说，公理系统自身的“完全性”和“无矛盾”（相容性）不能同时满足。这实际上也就是公理系统的基本工具性能力——可证性或演绎能力在自己的所有对象上的失效。

哥德尔第二定理是个元性质， 公理系统自身的资质“无矛盾性”或“相容性”不能由它自己证明。

一般情况下由于混含地理解了哥德尔不完全定理的层次性，哥德尔不完全定理被广泛地理解为数学和逻辑的形式系统中“存在真的但不可判定的命题”，在这种表述中，层次的深刻性被“真”这个本身就存在很大争议的术语替代了。这种表达实际上是把数论的“真”混用于逻辑“真”（这也是哥德尔不完全定理包含数论的原因），数学和逻辑的形式系统中“存在真的但不可判定的命题”实际上就是 “存在数论上是真的但逻辑上不可判定的命题”。

如果我们把“形式”这个术语理解为字母或“语言”这种符号表达形式，“可计算性算法”或“图灵机”（模式）就是这样一个“数学和逻辑的形式系统”。因此在我们看来，“存在真的但不可判定的命题”这种表达，也可以表达为“算法或图灵机中存在不可判定问题”，例如“停机问题”（一般所理解的“不可判定问题”undecidable problem是以“停机问题”方式作证明或解释的，我们认为，这种以悖论方式定义的方法，损害了可计算算法或图灵机的本质，是不可取的。）

我们已经指出，“停机问题”这种悖论性证明是以牺牲可计算性本身为代价的。因此我们提出与“不可判定问题”（Undecidable Problem）等价的NP定义。我们一方面坚持，算法或机器可判定的问题，也就是算法或机器可计算的问题（P判定即P计算），这样就把经典可计算理论作为基石而替代了对“真”的定义；另一方面，也就是相对于P的NP，我们定义，存在着没有算法或机器能进行判定或计算的问题，即“不确定性问题”（Nondeterministic Problem, NP）。这个定义是相对设定的。这样我们的NP定义区别于以往的基于“不确定性图灵机”（NDTM）所定义“不确定多项式时间”（Nondeterministic Polynomial Time），流行定义的NP问题仍是本质上的P问题，但我们的NP是在本质上与P相区别的，即在本质上相对于P的NP。

在严格的意义上，我们认为NP本质就是图灵对希尔伯特第十问题的解决。希尔伯特第十问题和图灵对希尔伯特第十问题的解决，我们合称为Entscheidungsproblem（“判断问题”—— “判断”的确定性或不确定性，是基于人的立场；“判定”的确定性Yes or No基于算法或机器）。P既是算法可计算的，也就是算法可判定的，即求解这类问题的算法同时也是对这类问题的可计算性的算法判定（P判定=P计算），在一般意义上也是可“判断”的。因此，Entscheidungsproblem是NP的本质。

在这种理解上，对于P问题，算法与逻辑是一致的，即P问题是算法可以判定的问题，是可以算法判定的存在或不存在可以确定性求解的算法的那一类问题，存在确定性求解的问题的算法也就是对这个问题可以算法求解的算法判定。相对应地，NP则是与P问题这个本质不同的问题，即在对P本质的否定性上的定义，也就是说，NP是不存在“可以判定‘存在算法或机器求解的算法’”的那些问题。

结合Entscheidungsproblem和哥德尔不完全定理，哥德尔不完全定理与我们的NP（Nondeterministic Problem）的概念具有内涵的一致性，可以说，我们的NP概念是Entscheidungsproblem和哥德尔不完全定理之间特殊等价形式。一方面，我们可以说：存在数论上是真的问题的陈述但无法以数论形式去进行逻辑判断（其真假），或者，存在算法语言表达的问题是不可以算法去判定（它是否是可计算的）。

从NP理论看哥德尔不完全定理，可以将哥德尔不完全定理表达为，一个公理系统内不存在“可以判定一个语法合适的命题是否是这个系统内的定理”的这样一个定理。这个表述与Entscheidungsproblem 具有一致性。

NP的本质是不可判断的，这个定义似乎容忍了“可能存在确定算法，但现在没有找到”这样一种流行的观念，这种观念错误与P定义是不相容，因为只要你承认“可能存在确定性算法”，就已经承认了这是P！流行的NP问题的定义都隐含了这种“讫题”或“循环定义”的错误，无法跳出事先暗中肯定NP=P的旋涡。（——这种陈述中所说的“可能”存在……这种超出经典逻辑的实在性和图灵机无限长纸带的观念，已经不在经典理论范围内了。）

  包括哥德尔本人在内的理论界对哥德尔不完全定理的意义和地位问题（即哥德尔不完全定理的哲学性质）一直存在难以梳理的论争，实质上这是在把“形式系统”等价于最基本的“语言”或“知识（形式）”的本质问题这个层次上的论争，这也就是最古老的哲学问题的延续，从柏拉图的实在论到中世纪的唯名论、唯实论，近现代以来的语言哲学、语法与语义关系，以及当前的人工智能基本问题等的论争的延续，这一切都深刻地与哲学上的“潜无穷”与“实无穷”的关系相关联。所有这些都是我们的NP理论后面的哲学背景。