P vs NP世紀(jì)難題顯示出在現(xiàn)有的計(jì)算機(jī)理論中存在著令人不安的困惑：一方面，書本中的NP問題理論部份無論是學(xué)習(xí)或教學(xué)都感到困難，以至于人們不得不一次又一次回頭去重新學(xué)習(xí)或思考，但或者失望而返，或者強(qiáng)迫自己服從這些權(quán)威論述；另一方面，現(xiàn)有的NP問題理論與實(shí)際工作幾乎完全脫節(jié)，甚至有人說完全可以不用此理論。進(jìn)一步，包含現(xiàn)有的NP問題的計(jì)算機(jī)理論無法與正蓬勃發(fā)展的人工智能理論銜接。

自2015年開設(shè)博客“不確定性的困惑與NP理論”以來，特別是2020年困難而特殊的一年，承蒙大家的熱情支持和慷慨的幫助！這里，我們與大家分享關(guān)于P vs NP問題研究工作總結(jié)性的文章：“NP問題是可計(jì)算的嗎？”-從“可計(jì)算性”的角度審視NP，希望對(duì)理清P vs NP問題的認(rèn)知糾纏有所幫助。

一，引言

二，NP定義溯源

三，現(xiàn)有的“可計(jì)算性”：“NP問題是窮舉法可計(jì)算的”

1，NP的形式定義

2，分析NP的形式定義

3，現(xiàn)有的“可計(jì)算性”所隱含的矛盾：“圖靈機(jī)”與“可計(jì)算問題”

四，圖靈的“可計(jì)算性”：“NP問題是窮舉法可計(jì)算的嗎？”

1，Entscheidungsproblem溯源

2，基于“可計(jì)算序列”的“判斷問題”

3，“可計(jì)算序列”，“計(jì)算機(jī)器”與“可計(jì)算問題”

4，“NP問題是窮舉法可計(jì)算的嗎？”

五，案例研究：現(xiàn)有的“圖靈機(jī)” vs圖靈的“計(jì)算機(jī)器”

六，“判定問題”與“判斷問題”：判斷的主體

七，結(jié)語

一，引言

在現(xiàn)有的計(jì)算機(jī)理論中，P（Polynomial time）指“圖靈機(jī)在多項(xiàng)式時(shí)間可判定的問題類”，但是對(duì)NP（Nondeterministic Polynomial time），情況卻復(fù)雜得多，首先有一個(gè)教科書式的定義，“NP是不確定性圖靈機(jī)在多項(xiàng)式時(shí)間可判定的問題類”（NP is the class of problems decidable by Non-Deterministic Turing Machine (NDTM ) in polynomial time -定義1），后來又發(fā)展出一個(gè)更通俗化的定義，“NP是圖靈機(jī)在多項(xiàng)式時(shí)間可驗(yàn)證的問題類”（NP is the class of problems verifiable by TM in polynomial time - 定義2）。于是，P vs NP問題被一般性表達(dá)為：NP=P？即多項(xiàng)式時(shí)間可驗(yàn)證的問題（NP）是多項(xiàng)式時(shí)間可判定的問題嗎（P）？[1][2]

P vs NP問題成為計(jì)算機(jī)理論的重大的未解難題，還被Clay Mathematics Institute收錄為七個(gè)千禧年難題之一。Gasarch于2002年，2012年和2019年對(duì)P vs NP問題的前途進(jìn)行了三次調(diào)查[3]，表明人們?yōu)閷ふ仪蠼釴P問題的多項(xiàng)式時(shí)間算法付出了巨大的努力，以求一舉解決P vs NP難題，但是迄今為止并沒有出現(xiàn)有價(jià)值的進(jìn)展方向。

Hemaspaandra在介紹Gasarch的第二次調(diào)查時(shí)說：我希望在遙遠(yuǎn)的未來，當(dāng)人們讀到這四篇文章（指介紹P vs NP問題的四篇文章），可以幫助他們了解，在“P vs NP”還沒得到解決的黑暗年代里人們的思想狀態(tài)（I hope that people in the distant future will look at these four articles to help get a sense of people’s thoughts back in the dark ages when P versus NP had not yet been resolved) [4]。

P vs NP問題的難點(diǎn)集中在對(duì)NP的認(rèn)知上，表達(dá)為NP定義，關(guān)于NP的定義纏繞了計(jì)算機(jī)基本理論幾十年，比如，Scott Aaronson在博客“The Scientific Case for P≠NP”說：似乎有一個(gè)“看不見的電圍欄”把P問題與NP完全的問題區(qū)分開(there seems to be an "invisible electric fence separating the problems in P from the NP-complete ones) [5]。

由流行的NP定義得出：“NP問題是窮舉法可計(jì)算的”，也就是說，NP定義的本質(zhì)是對(duì)NP問題的“可計(jì)算性”的判斷。然而，“可計(jì)算性的判斷”是可計(jì)算性理論的核心議題，整個(gè)計(jì)算機(jī)理論由此展開，可是對(duì)于“NP問題的可計(jì)算性的判斷”，如此重要的議題，卻幾乎未見學(xué)術(shù)界展開討論過。本文追本溯源回到圖靈1936年那篇奠基可計(jì)算性理論的論文《論可計(jì)算數(shù)及其在判定問題上的應(yīng)用》（On Computable Numbers, with an Application to the Entscheidungsproblem）[6]，對(duì)比現(xiàn)有的“可計(jì)算性”與圖靈的“可計(jì)算性”，解讀流行NP定義，探討其對(duì)NP問題的“可計(jì)算性”判斷的有效性，我們將看到對(duì)此質(zhì)疑：“NP問題是窮舉法可計(jì)算的嗎？”

二，NP定義溯源

NP作為概念“Non-deterministic Polynomial time”的提出源于柯克1971年那篇奠基性的論文，文中柯克提出后人稱之的“柯克定理”，即論文中的定理1 [7]：

定理1：如果一個(gè)符號(hào)串集合S被某種不確定性圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)接受，那末S可以被P-歸約到{析取重言式}。

（Theorem 1 If a set S of strings is accepted by some nondeterministic Turing machine within polynomial time, then S is P-reducible to {DNF tautologies}.）

由此，得出NP的第一個(gè)流行定義：

定義1 : NP is the class of problems decidable by NDTM in polynomial time。

在柯克的論文中，NDTM原指由“神諭機(jī)（Oracle Machine）”與“圖靈機(jī)（Turing Machine）”混合而成的“查詢機(jī)（Query Machine）”，查詢機(jī)的計(jì)算行為被解釋為：對(duì)于一個(gè)NP問題實(shí)例，神諭機(jī)“可解”，此“解”可由圖靈機(jī)多項(xiàng)式時(shí)間“驗(yàn)證”。然而，由于神諭機(jī)不是構(gòu)造性的機(jī)器模型，在現(xiàn)實(shí)中并不存在，為了將神諭機(jī)從NDTM中排除，學(xué)界遂將NDTM的計(jì)算行為解釋為“猜測＋驗(yàn)證” [8]，即對(duì)于一個(gè)NP問題實(shí)例，NDTM在多項(xiàng)式時(shí)間“猜測”出一個(gè)候選解，并能在多項(xiàng)式時(shí)間“驗(yàn)證”。經(jīng)過這樣的解釋，NDTM就從“查詢機(jī)”變成了現(xiàn)在的“多選擇的NDTM”，即相對(duì)于在計(jì)算的下一步只有“唯一的選擇”的TM，NDTM可以有“多選擇” [9]。于是，得到NP的第二個(gè)流行定義：

定義2 : NP is the class of problems verifiable by TM in polynomial time。

定義1與定義2被認(rèn)為等價(jià)[10]，NDTM又被解釋為與TM等價(jià)，“Every nondeterministic Turing machine has an equivalent deterministic Turing machine”（Sipser書，Theorem 3.16）， 于是有了一個(gè)非形式的“承認(rèn)”：TM在指數(shù)時(shí)間內(nèi)模擬NDTM的計(jì)算。

由此人們很快就認(rèn)可，NDTM的計(jì)算行為與“窮舉法”等同，這樣NP又被解釋為“NP是窮舉法可計(jì)算的問題類”，畢竟P與NP不同，于是就有了“NP問題是可計(jì)算的，但難計(jì)算的”這樣的流行觀念。

不管以后的解釋如何，在直覺認(rèn)知上，NP與P是不同的，但是NP的定義又給人NP與P等價(jià)的指望，這就是P vs NP問題的困難之源。

三，流行的“可計(jì)算性”：“NP問題是窮舉法可計(jì)算的”

首先，我們討論NP的形式定義。

1，NP的形式定義

這里我們考慮Papadimitriou的書“計(jì)算復(fù)雜性”的第9章給出的NP的形式定義[11]，Cook在為Clay Mathematics Institute介紹P vs NP問題時(shí)也給出了類似的定義[1]：

- 令R為二進(jìn)制字符串的關(guān)系；即，讓R為一組有序?qū)?x,y)的集合，其中x和y是二進(jìn)制字符串。如果存在確定性圖靈機(jī)在多項(xiàng)式時(shí)間內(nèi)判定給定的(x,y)是否在R中，我們則說R是“多項(xiàng)式可判定”。如果k >= 1，使得對(duì)于R中的所有(x,y)，y的長度（我們寫為| y |）最大為|x|^k，則R是“多項(xiàng)式平衡”。(Let R be a relation on binary strings; i.e., let R be a set of ordered pairs (x,y) where x and y are binary strings. We say that R is "polynomially decidable" if there is a deterministic Turing machine that decides in polynomial time where a given (x,y) is in R. We also say that R is "polynomially balanced" if there is some k >= 1 such that for all (x,y) in R, the length of y (which we write as |y|) is at most |x|^k.)

- 現(xiàn)在我們準(zhǔn)備定義NP。語言L在NP中，當(dāng)且僅當(dāng)存在多項(xiàng)式可判定且多項(xiàng)式平衡的關(guān)系R，使得語言L = {x : (x,y)在R中存在y}時(shí)。(Now we are ready to define NP. A language L is in NP if and only if there is a polynomially decidable and polynomially balanced relation R such that L = {x : (x,y) is in R for some y}.)

2，分析NP的形式定義

NP的形式定義涉及集合L和R，讓我們以SAT，典型的NP問題為例，從解讀L和R開始。

2.1集合L和R

考慮2個(gè)SAT實(shí)例：

f1 = (x1∨x2∨x3)∧(x1∨x2∨￢x3)∧(￢x1∨￢x2∨ x3)∧(￢x1∨x2∨x3)，f1有3個(gè)變元，共2^3=8個(gè)變元賦值組合，其中4個(gè)是f1的解，R = {(f1,(0 1 0)), (f1,(0 1 1)), (f1,(1 0 1)), (f1,(1 1 1))}。

f2= x1∧?x1, 1個(gè)變元，共有2個(gè)變元賦值的組合，f2無解，R = ?。

對(duì)于L，f1可滿足，在L中；f2不可滿足，不在L中，故L = { …, f1, …}。

所以，R是SAT的給定實(shí)例的所有解的集合，而L是SAT的所有可滿足的實(shí)例的集合：

- R = {(x,y) : x是SAT的實(shí)例，y是x的解}

- L = {x : 存在某個(gè)y，使得(x,y) 在R中}

下面我們按照這個(gè)方法定義SAT，很快能看到，P面向“判定問題”，而NP面向“判斷問題”。

2.2 “判定問題”與“判斷問題”

記集合A = {x：G(x)表示x滿足某種性質(zhì)}，表達(dá)元素x與集合A的所屬關(guān)系，即“整體中個(gè)體”，而判斷x是否在A中，即判斷元素x是否具有性質(zhì)G(x)。

從這個(gè)理解出發(fā)，SAT呈現(xiàn)出二個(gè)層次上的定義：

-判定問題：窮舉法判定SAT問題的給定實(shí)例x是否可滿足。這相當(dāng)于，窮舉法判定x的給定候選解y是否在R中。

-判斷問題：如果窮舉法可以判定SAT實(shí)例（R），那么窮舉法是否可以判定SAT問題（L）？

可見，“判定問題”面向“實(shí)例”（個(gè)體，R），而“判斷問題”面向“問題”（整體，L），所以NP的形式定義是基于對(duì)“判斷問題”的回答。實(shí)際上，我們也能看到，這個(gè)回答才是造成現(xiàn)有的NP定義的困難的根源。

對(duì)于“判定問題”，通過枚舉SAT實(shí)例x的所有候選解y，重復(fù)調(diào)用多項(xiàng)式時(shí)間驗(yàn)證解的圖靈機(jī)M，就可以在指數(shù)時(shí)間判定x是否可滿足，所以窮舉法對(duì)判定SAT實(shí)例x具有可計(jì)算性。

但要注意，這個(gè)意義上的“窮舉法”并沒有產(chǎn)生一個(gè)新的圖靈機(jī)與之對(duì)應(yīng)，就是說，不過是重復(fù)調(diào)用多項(xiàng)式時(shí)間驗(yàn)證解的圖靈機(jī)M，因此這里的“指數(shù)時(shí)間”只是表達(dá)重復(fù)調(diào)用M，是一個(gè)由“人”暗中定義了的“指數(shù)時(shí)間復(fù)雜度”。所以，“判定問題”的本質(zhì)是“P問題”。

根據(jù)NP的形式定義，“語言L在NP中，當(dāng)且僅當(dāng)存在多項(xiàng)式可判定且多項(xiàng)式平衡的關(guān)系R，使得語言L = {x : (x,y)在R中存在y}”，就是說，“窮舉法”判定SAT實(shí)例與“窮舉法”判定SAT問題等價(jià)，換句話說，在“判定問題”與“判斷問題”之間建立起了越界的等價(jià)關(guān)系！

這也正是NP的非形式定義1與定義2“等價(jià)”所表達(dá)的意義：“NP is the class of problems verifiable by TM in polynomial time”與“NP is the class of problems decidable by NDTM in polynomial time”等價(jià)。

所以，流行NP定義是對(duì)NP問題的“可計(jì)算性”的直接肯定，而非論證，實(shí)例與問題的關(guān)系從“整體中的個(gè)體”變成了“個(gè)體即整體”，“判斷問題”因此被取消了，從而失去了揭示NP本質(zhì)的可能性，暗含NP=P。下面我們從現(xiàn)有的“可計(jì)算性”觀念中追究更一般性的原因。

3，流行的“可計(jì)算性”所的隱含的矛盾：“圖靈機(jī)”與“可計(jì)算問題”

在現(xiàn)有的計(jì)算機(jī)理論中，“可計(jì)算問題”被解讀為，“可計(jì)算問題是由’停機(jī)’的圖靈機(jī)計(jì)算的問題”，圖靈機(jī)的“無限長的紙帶”被解讀為“無限的時(shí)空”，所以圖靈機(jī)的計(jì)算被解釋為“不計(jì)時(shí)空開銷”。這樣的“可計(jì)算問題”在“理論上”似乎是可計(jì)算的，但“物理上”卻不一定是可計(jì)算的。

“圖靈機(jī)模型使用無限長紙帶作為其無限內(nèi)存，有一個(gè)讀寫頭。最初，輸入字符串被放置紙帶上，紙帶的其他方格均為空白。機(jī)器將繼續(xù)計(jì)算，直到?jīng)Q定產(chǎn)生輸出為止。通過進(jìn)入指定的接受和拒絕狀態(tài)來判斷是否接受和拒絕輸入，如果圖靈機(jī)不進(jìn)入接受或拒絕狀態(tài)，則將永遠(yuǎn)持續(xù)下去，永不停止。[10]（Sipser書，Theorem 3.16）”

- The Turing machine model uses an infinite tape as its unlimited memory. It has a tape head that can read and write symbols and move around on the tape. Initially the tape contains only the input string and is blanc everywhere else. If the machine needs to store information, it may write this information on the tape. To read the information that it has written, the machine can move its head back over it. The machine continues computing until it decides to produce an output. The outputs accept and rejet are obtained by entering designated accepting and rejecting states. If it doesn’t enter an accepting or a rejecting state, it will go on forever, never halting.

既然圖靈機(jī)的計(jì)算“不計(jì)時(shí)空開銷”，那么“窮舉法”計(jì)算NP問題的實(shí)例與計(jì)算NP問題（任意實(shí)例）就沒有區(qū)別，這就是“判定問題”與“判斷問題”之間越界的等價(jià)關(guān)系的來源！

現(xiàn)在讓我們追本溯源回到圖靈的可計(jì)算性理論，考察“NP問題是窮舉法可計(jì)算的”有效性。

四，圖靈的“可計(jì)算性”：“NP問題是窮舉法可計(jì)算的嗎？”

作為計(jì)算機(jī)理論的核心概念，“可計(jì)算性”表達(dá)了“算法”普遍性的解決問題的過程性能力，對(duì)這種過程性能力的考察被數(shù)學(xué)家隱含地表達(dá)出來，這就是著名的希爾伯特（David Hilbert 1862─1943）的Entscheidungsproblem：是否存在“通用過程”來判定任何可定義的數(shù)學(xué)問題可解。

Entscheidungsproblem這一詞由于歷史時(shí)間不同，具有不同的具體表達(dá)形式。

1，Entscheidungsproblem溯源

Entscheidungsproblem源于希爾伯特1900年所作的《數(shù)學(xué)問題》的著名講演，其中提出了數(shù)學(xué)理論中的23個(gè)最困難的問題，第10問題是這樣說的[13]: Given a Diophantine equation with any number of unknown quantities and with rational integral numerical coefficients: To devise a process according to which it can be determined in a finite number of operations whether the equation is solvable in rational integers.

作為一個(gè)大數(shù)學(xué)家希爾伯特并沒有用“數(shù)學(xué)方法”、“函數(shù)”或“形式方法”這樣現(xiàn)成的術(shù)語，而是問：能否“設(shè)計(jì)一個(gè)過程”（To devise a process）來“判定”（determine）任何一個(gè)丟番圖方程問題是否可解？

在1936年的文章中，圖靈證明：不存在“通用過程”判定任何一階謂詞公式可證。

2，基于“可計(jì)算序列”的“判斷問題”

為此，圖靈理解性說[6] ：對(duì)這樣一個(gè)“通用過程”的問題可以表達(dá)為通用過程判定給定的整數(shù)n是否具有性質(zhì)G(n)的問題（比如，G(n)可能表示“n是可滿足的’’或“n是一個(gè)可證明公式的Godel表達(dá)），這相當(dāng)于計(jì)算一個(gè)數(shù)，如果G(n)為真，其第n個(gè)數(shù)字為1；如果G(n)為假，其第n個(gè)數(shù)字為0。”（For each of these "general process" problems can be expressed as a problem concerning a general process for determining whether a given integer n has a property G(n) [e.g. G{n) might mean "n is satisfactory" or "n is the Godel representation of a provable formula"], and this is equivalent to computing a number whose n-th figure is 1 if G(n) is true and 0 if it is false.）

與上述基于“語言”的NP的形式定義相比，圖靈引入了“可計(jì)算數(shù)（序列）”（computable numbers/sequence）概念，表示機(jī)器寫下的所有實(shí)例的計(jì)算結(jié)果，而將給定實(shí)例的計(jì)算結(jié)果置于此序列中，表達(dá)了實(shí)例與問題的“整體中個(gè)體”的關(guān)系，也就是說，“判定問題”包含在“判斷問題”中。

“可計(jì)算數(shù)（序列）”成為圖靈工作的紅線，貫穿于整個(gè)論文中，正如Charles Petzold在其書The Annotated Turing所說[12]:

- “盡管解決Entscheidungsproblem確實(shí)是圖靈寫這篇文章的動(dòng)機(jī)，但是這篇長篇大論本身講的卻是’可計(jì)算數(shù)’。在圖靈的定義中，可計(jì)算數(shù)就是可以使用機(jī)器計(jì)算的數(shù)。論文前面60%的內(nèi)容都是對(duì)可計(jì)算數(shù)的探索。”

讓我們考察圖靈是如何從“可計(jì)算數(shù)（序列）”出發(fā)定義“可計(jì)算性”的。

3，“可計(jì)算序列”，“計(jì)算機(jī)器”與“可計(jì)算問題”

圖靈在論文開篇提出“可計(jì)算數(shù)”（computable numbers），強(qiáng)調(diào)是由機(jī)器寫下來的 [6] ：

-按照我的定義，一個(gè)數(shù)是可計(jì)算的，如果它的十進(jìn)制的表達(dá)能被機(jī)器寫下來。（According to my definition, a number is computable if its decimal can be written down by a machine.）

接著，圖靈將人計(jì)算實(shí)數(shù)與機(jī)器計(jì)算過程進(jìn)行比較，構(gòu)造出作為現(xiàn)代計(jì)算機(jī)模型的“計(jì)算機(jī)器”（computing machine），寫下“可計(jì)算數(shù)（序列）”（computable number/séquence)：

-如果一臺(tái)機(jī)器打印兩類符號(hào)，第一類（稱為數(shù)字）全是0和1，其它被稱為第二類符號(hào)，則機(jī)器將被稱為“計(jì)算機(jī)器”。如果給機(jī)器裝置一條空白紙帶，讓它運(yùn)動(dòng)起來，從正確的初始m－格局出發(fā)，機(jī)器打印的第一類符號(hào)的子序列稱作機(jī)器計(jì)算的序列；在表達(dá)為二進(jìn)制的十進(jìn)制實(shí)數(shù)前放上小數(shù)點(diǎn)，稱作機(jī)器計(jì)算的數(shù)。（If an a-machine prints two kinds of symbols, of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a computing machine. If the machine is supplied with a blank tape and set in motion, starting from the correct initial m-configuration, the subsequence of the symbols printed by it which are of the first kind will be called the sequence computed by the machine. The real number whose expression as a binary decimal is obtained by prefacing this sequence by a decimal point is called the number computed by the machine.）

圖靈進(jìn)一步區(qū)分Circular machine和Circle-free machine：

-如果計(jì)算機(jī)器只寫下第一類有限數(shù)目的符號(hào)，被稱作“Circular”；否則，被稱作“circle-free”。（If a computing machine never writes down more than a finite number of symbols of the first kind it will be called circular. Otherwise it is said to be circle-free.）

然后，再用Circle-free machine的計(jì)算過程明確定義“可計(jì)算數(shù)（序列）”（Computable sequences/numbers）

-一個(gè)序列被說成“可計(jì)算的”，如果能夠通過一臺(tái)“circle-free machine”計(jì)算而得。一個(gè)數(shù)是“可計(jì)算的”，如果它與由“circle-free machine”計(jì)算的數(shù)只差一個(gè)整數(shù)。（A sequence is said to be computable if it can be computed by a circle-free machine. A number is computable if it differs by an integer from the number computed by a circle- free machine.）

并且說：

-為了避免混淆，我們更經(jīng)常說可計(jì)算序列，而不是可計(jì)算數(shù)。（We shall avoid confusion by speaking more often of computable sequences than of computable numbers.）

這樣，“可計(jì)算序列”在“算法（計(jì)算機(jī)器）”與“問題”之間建立起可能存在的某種“實(shí)質(zhì)性”的聯(lián)系，“可計(jì)算問題是計(jì)算機(jī)器寫下可計(jì)算序列的問題”。由此，圖靈的“可計(jì)算性”表達(dá)了“通用性”，“整體性”和“實(shí)時(shí)性”。

對(duì)比上述流行的“可計(jì)算問題”，圖靈定義的“可計(jì)算問題”不僅在“理論”上是可計(jì)算的，而且在“物理”上也是可計(jì)算的

4，“NP問題是窮舉法可計(jì)算的嗎？”

從圖靈的“可計(jì)算性”的角度，SAT表達(dá)為“判斷問題”:

-判斷問題：是否存在計(jì)算機(jī)器判定SAT的給定實(shí)例fn可滿足，這相當(dāng)于計(jì)算序列αL = G(f1)G(f2)G(f3)... G(fn)…（G(fn)表示fn是可滿足的實(shí)例），如果G(fn)=1，fn是可滿足的；否則，fn是不可滿足的？

所以考察“窮舉法”對(duì)SAT問題是否具有可計(jì)算性，就是考察“窮舉法”能否寫下SAT問題的可計(jì)算序列αL = G(f1)G(f2)G(f3)…G(fn)…。

如以上分析，“窮舉法”判定SAT的給定實(shí)例，是通過重復(fù)調(diào)用多項(xiàng)式時(shí)間驗(yàn)證解的計(jì)算機(jī)器M而具有“指數(shù)時(shí)間復(fù)雜度”，所以“窮舉法”的本質(zhì)就是計(jì)算機(jī)器M，而“窮舉法”的指數(shù)增長的計(jì)算開銷能否勝任SAT的實(shí)例規(guī)模的增長，即能否計(jì)算αL = G(f1)G(f2)G(f3)…G(fn)…成為了“問題”，換句話說，多項(xiàng)式時(shí)間驗(yàn)證解的計(jì)算機(jī)器M對(duì)SAT問題是否具有可計(jì)算性成為了“問題”，是有問題：“SAT是窮舉法可計(jì)算的嗎？”

實(shí)際上，對(duì)“SAT是窮舉法可計(jì)算的嗎？”的判斷進(jìn)入了計(jì)算復(fù)雜性理論的論域，而對(duì)SAT的“可計(jì)算性”的一般性判斷則與圖靈論文的主題希爾伯特的Entscheidungsproblem密切相關(guān)，需要專門討論，不是本文的主題。

五，案例研究：現(xiàn)有的“圖靈機(jī)” vs圖靈的“計(jì)算機(jī)器”

為了進(jìn)一步理解現(xiàn)有的“可計(jì)算性”與圖靈的“可計(jì)算性”的區(qū)別，我們以判定任意自然數(shù)的奇偶性為例，對(duì)比“圖靈機(jī)”與圖靈的“計(jì)算機(jī)器”。

1，“圖靈機(jī)”

判定問題：判定所有的自然數(shù)n的奇偶性，這相當(dāng)于判定任意的自然數(shù)n是否在偶數(shù)集合A中，A = {n : mod(n, 2)=0}。

比如n=2，mod(2, 2)=0，故2在A中；n=3，mod(3, 2)/=0，故3不在A中。

這里，假設(shè)輸入的自然數(shù)用“真數(shù)”表示：1（1），2（11），3（111），。。，；輸出1表示偶數(shù)；輸出0表示奇數(shù)。

圖靈機(jī)M1的規(guī)則表：

q1, 1, #, R, q2

q2, 1, #, R, q1

q1, #, 1, R, qY

q2, #, 0, R, qN

q1表示“初始狀態(tài)”，qYt表示“接受狀態(tài)”, qN表示“拒絕狀態(tài)”，qY與qN都是“停機(jī)狀態(tài)”。

模擬M在輸入（n=2）的運(yùn)行：

開始的紙帶放置11（Rule）：

1 1 # # # …

內(nèi)態(tài)的變化：

q1 q2 q1 qY.

紙帶的變化：

# # 1 # # …

模擬M在輸入（n=3）的運(yùn)行：

開始的紙帶放置任給的一個(gè)自然數(shù)：

1 1 1 # # …

內(nèi)態(tài)的變化：

q1 q2 q1 q2 qN.

紙帶的變化：

# # # 0 # …

2，圖靈的“計(jì)算機(jī)器”

根據(jù)圖靈對(duì)“判斷問題”的表達(dá)：

判斷問題：判定所有的自然數(shù)n的奇偶性（G(n)表示n是偶數(shù)，n mod 2 = 0），這相當(dāng)于計(jì)算序列010101…，如果G(n)為真（偶數(shù)），序列的第n個(gè)數(shù)字為1；如果G(n)為假(奇數(shù))，序列的第n個(gè)數(shù)字為0。

其可計(jì)算序列記為，α = G(1)G(2)G(3)…G(n)，。。。= 010101…

G(1)=0 (n=1,奇數(shù)）

G(2)=1（n=2,偶數(shù)）

G(3)=0 (n=3,奇數(shù))

。。。

圖靈在論文中給出的第一個(gè)“計(jì)算機(jī)器”的例子就是計(jì)算序列010101…，但圖靈是將此序列作為十進(jìn)制數(shù)0.333…的二進(jìn)制數(shù)表示，所以沒有考慮輸入數(shù)據(jù)，紙帶的輸入只是空白符號(hào)“#”（blank），其對(duì)應(yīng)的“計(jì)算機(jī)器”的規(guī)則表如下：

q1, # , 0, R, q2

q2, # , # , R, q3

q3, # , 1, R, q4

q4,# , # , R, q1

模擬此機(jī)器的運(yùn)行：

# # # # # # …

q1 q2 q3 q4 q1 q2 …

0 # 1 # 0 # …

我們將序列010101…作為對(duì)所有自然數(shù)（1,2,3,…）奇偶性的判斷結(jié)果，紙帶上的輸入數(shù)據(jù)是用“真數(shù)”表示的所有自然數(shù)：1（1），2（11），3（111），。。，；輸出1表示偶數(shù)；輸出0表示奇數(shù)。

所以需要上述計(jì)算機(jī)器M1的規(guī)則表略作修改成M2：

q1, 1, #, R, q2

q2, 1, #, R, q1

q1, #, 1, R, q1

q2, #, 0, R, q1

此機(jī)器的初始狀態(tài)是q1，沒有停機(jī)狀態(tài)。在q1狀態(tài)下遇空白符“#”，寫下“1”，表示輸入的自然數(shù)是偶數(shù)，然后回到初始狀態(tài)q1；q2狀態(tài)下遇空白符“#”，寫下“0”，表示輸入的自然數(shù)是奇數(shù)，然后回到初始狀態(tài)q1，繼續(xù)判斷紙帶上的下一個(gè)自然數(shù)。

模擬此“圖靈機(jī)”的運(yùn)行：

開始的紙帶：

1 # 1 1 # 1 1 1 # …

內(nèi)態(tài)的變化：

q1 q2 q1 q2 q1 q1 q2 q1 q2 q1, …

紙帶的變化：

# 0 # # 1 # # # 0 …

可見，現(xiàn)有的“圖靈機(jī)”（M1）與圖靈的“計(jì)算機(jī)器”（M2）之間存在著微妙的差別：“計(jì)算機(jī)器”計(jì)算完一個(gè)實(shí)例然后回到初始狀態(tài)，“不停機(jī)”繼續(xù)計(jì)算下一個(gè)實(shí)例，“無限長的紙帶”對(duì)應(yīng)“無限長的可計(jì)算序列”（circle-free machine），表達(dá)計(jì)算機(jī)器的計(jì)算能力的“通用性”。所以，“計(jì)算機(jī)器”雖然沒有對(duì)計(jì)算一個(gè)實(shí)例的時(shí)空開銷進(jìn)行規(guī)定，但是并非指計(jì)算一個(gè)實(shí)例“不計(jì)時(shí)空開銷”。

而現(xiàn)有的“圖靈機(jī)”加入了“停機(jī)狀態(tài)”，計(jì)算完一個(gè)實(shí)例就“停機(jī)”（接受與拒絕），遂將“無限長的紙帶”解讀為計(jì)算一個(gè)實(shí)例“不計(jì)時(shí)空開銷”。

六，集合與判斷：判斷的主體

如上述分析，NP定義的本質(zhì)是對(duì)NP問題的“可計(jì)算性”的判斷，但是流行的NP定義將“判定問題”等價(jià)于“判斷問題”，直接得出“NP問題是可計(jì)算的”判斷。我們從集合與判斷的角度，進(jìn)一步分析其原因。

康托最初給出的集合定義 [14]：

- 集合是“我們感知或思想到的”不同的對(duì)象的聚集而成的整體，這些對(duì)象稱為集合的元素。

- 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.

就是說，集合表達(dá)的是對(duì)元素與集合的所屬關(guān)系，即“整體中個(gè)體”的“判斷”。

判斷涉及到“判斷的主體”，在一般情況下“主體”指“人”，人運(yùn)用感知或思想進(jìn)行判斷。當(dāng)人借助于數(shù)學(xué)和邏輯進(jìn)行判斷，論域是“數(shù)學(xué)”；但是人當(dāng)借助于“算法”來進(jìn)行判斷時(shí)，判斷的“主體”成了“機(jī)器”，論域就從“數(shù)學(xué)”轉(zhuǎn)移到了“算法”。雖然數(shù)學(xué)和算法都使用符號(hào)，但其組織性質(zhì)完全不同，數(shù)學(xué)是純粹的形式關(guān)系，與“物理”無關(guān)；而算法則一定是“實(shí)時(shí)”（Actual Time）過程，與時(shí)空有關(guān)。

在流行的NP定義中，“判定問題”指“窮舉法判定NP問題的給定實(shí)例x是否可滿足”，判斷的主體是“圖靈機(jī)”（算法），算法與時(shí)空有關(guān)，然而在現(xiàn)有的可計(jì)算性理論中，圖靈機(jī)的“無限長的紙帶”被解釋為“不計(jì)時(shí)空”，“圖靈機(jī)”因此失去了算法的“物理”性質(zhì)，實(shí)際上成為了“神喻機(jī)”，也就是說，判斷的主體從“圖靈機(jī)”偷換成了“神喻機(jī)”！所以，“窮舉法”判定NP問題的實(shí)例與判定NP問題就沒有了區(qū)別，直接得出“NP問題是可計(jì)算的”判斷，從而取消了“人”作為判斷的主體的“判斷問題”，流行NP定義暗含NP=P。

可見，在現(xiàn)有的“可計(jì)算性”理論中，存在著判斷“主體”的混淆，導(dǎo)致對(duì)個(gè)體與整體關(guān)系認(rèn)知的混淆，暗中用“個(gè)體即整體”替代了“整體中個(gè)體”，這正是流行NP定義所隱藏的認(rèn)知錯(cuò)誤的來源，所謂“數(shù)學(xué)家的誤解” [15]。

七，結(jié)語

我們追本溯源回到圖靈1936年那篇奠基可計(jì)算性理論的論文《論可計(jì)算數(shù)及其在判定問題上的應(yīng)用》，解讀流行的NP定義，質(zhì)疑“NP問題是窮舉法可計(jì)算的”流行觀點(diǎn)。

通過對(duì)比分析，我們指出現(xiàn)有的“可計(jì)算性”與圖靈的“可計(jì)算性”之間有出入。首先，體現(xiàn)在對(duì)NP問題的二種表達(dá)中：

- 基于“語言”的NP問題；

- 基于“可計(jì)算序列”的NP問題。

然后是“圖靈機(jī)”與圖靈定義的“計(jì)算機(jī)器”之間存在著微妙的差別：

- “圖靈機(jī)”完成對(duì)一個(gè)實(shí)例的計(jì)算而“停機(jī)”，“無限長的紙帶”被解釋為計(jì)算一個(gè)實(shí)例“不計(jì)時(shí)空開銷”；

- 圖靈的“計(jì)算機(jī)器”完成對(duì)一個(gè)實(shí)例的計(jì)算后回到初始狀態(tài)，然后“不停機(jī)”繼續(xù)計(jì)算下一個(gè)實(shí)例。

由此導(dǎo)致關(guān)于“可計(jì)算問題”的二種觀點(diǎn)：

- 現(xiàn)有的“可計(jì)算問題是圖靈機(jī)不計(jì)時(shí)空開銷計(jì)算但能停機(jī)的問題”，在“物理”上不必是可計(jì)算的。

- 圖靈的“可計(jì)算問題是計(jì)算機(jī)器能寫下可計(jì)算序列的問題”，在“理論”和“物理”上的可計(jì)算性是一致的。

我們從集合與判斷的角度，分析在現(xiàn)有的“可計(jì)算性”理論中存在著判斷“主體”的混淆，導(dǎo)致“判定問題”與“判斷問題”的混淆。我們認(rèn)為欲解決P vs NP問題，需要正視對(duì)NP問題的“可計(jì)算性”的“判斷問題”，這就意味著需要追本溯源審視對(duì)“圖靈機(jī)”，“可計(jì)算性”，“計(jì)算復(fù)雜性，“停機(jī)問題”等計(jì)算機(jī)理論的基本議題的認(rèn)識(shí)。本文所介紹的工作就是這方面的初步嘗試。

我們的工作提示，圖靈的著作和工作雖然已經(jīng)近百年了，盡管在技術(shù)實(shí)踐上取得了巨大的成就，但在圖靈的主要理論基礎(chǔ)上并沒有取得跨越性的進(jìn)步，甚至已經(jīng)被作為計(jì)算機(jī)理論圣經(jīng)的“圖靈機(jī)”仍然蒙著一層神秘的面紗，比如問：

- 為什么現(xiàn)在的“圖靈機(jī)”與圖靈的“計(jì)算機(jī)器”之間存在著微妙差別？

- 為什么“可計(jì)算序列（數(shù)）”的概念從現(xiàn)有的計(jì)算理論中消失了？

圖靈處在世界格局重構(gòu)的年代，數(shù)學(xué)和科學(xué)理論的大廈己經(jīng)聳立，工業(yè)技術(shù)與純粹理論正在融匯而走向一個(gè)全新的信息時(shí)代，圖靈有幸成為了這個(gè)轉(zhuǎn)折點(diǎn)，我們並不期望直接從圖靈的論著中找到現(xiàn)成的答案，而是希望通過他的著作去理解他深刻而隱秘的思想，從中獲取靈感，用我們的智慧去參與和回應(yīng)時(shí)代面臨的挑戰(zhàn)，比如P vs NP問題的挑戰(zhàn)。

原文標(biāo)題：“NP問題是可計(jì)算的嗎？” - 從“可計(jì)算性”的角度審視NP

文章出處：【微信公眾號(hào)：通信信號(hào)處理研究所】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。

責(zé)任編輯：haq