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

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

一，引言

二，NP定義溯源

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

1，NP的形式定義

2，分析NP的形式定義

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

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

1，Entscheidungsproblem溯源

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

3，“可計算序列”，“計算機器”與“可計算問題”

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

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

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

七，結(jié)語

一，引言

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

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

Hemaspaandra在介紹Gasarch的第二次調(diào)查時說：我希望在遙遠的未來，當(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問題的難點集中在對NP的認(rèn)知上，表達為NP定義，關(guān)于NP的定義纏繞了計算機基本理論幾十年，比如，Scott Aaronson在博客“The Scientific Case for P≠NP”說：似乎有一個“看不見的電圍欄”把P問題與NP完全的問題區(qū)分開(there seems to be an "invisible electric fence separating the problems in P from the NP-complete ones) [5]。

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

二，NP定義溯源

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

定理1：如果一個符號串集合S被某種不確定性圖靈機在多項式時間內(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的第一個流行定義：

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

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

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

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

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

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

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

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

1，NP的形式定義

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

- 令R為二進制字符串的關(guān)系；即，讓R為一組有序?qū)?x,y)的集合，其中x和y是二進制字符串。如果存在確定性圖靈機在多項式時間內(nèi)判定給定的(x,y)是否在R中，我們則說R是“多項式可判定”。如果k >= 1，使得對于R中的所有(x,y)，y的長度（我們寫為| y |）最大為|x|^k，則R是“多項式平衡”。(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)存在多項式可判定且多項式平衡的關(guān)系R，使得語言L = {x : (x,y)在R中存在y}時。(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個SAT實例：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

“圖靈機模型使用無限長紙帶作為其無限內(nèi)存，有一個讀寫頭。最初，輸入字符串被放置紙帶上，紙帶的其他方格均為空白。機器將繼續(xù)計算，直到?jīng)Q定產(chǎn)生輸出為止。通過進入指定的接受和拒絕狀態(tài)來判斷是否接受和拒絕輸入，如果圖靈機不進入接受或拒絕狀態(tài)，則將永遠持續(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.

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

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

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

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

Entscheidungsproblem這一詞由于歷史時間不同，具有不同的具體表達形式。

1，Entscheidungsproblem溯源

Entscheidungsproblem源于希爾伯特1900年所作的《數(shù)學(xué)問題》的著名講演，其中提出了數(shù)學(xué)理論中的23個最困難的問題，第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.

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

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

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

為此，圖靈理解性說[6] ：對這樣一個“通用過程”的問題可以表達為通用過程判定給定的整數(shù)n是否具有性質(zhì)G(n)的問題（比如，G(n)可能表示“n是可滿足的’’或“n是一個可證明公式的Godel表達），這相當(dāng)于計算一個數(shù)，如果G(n)為真，其第n個數(shù)字為1；如果G(n)為假，其第n個數(shù)字為0?！保‵or 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的形式定義相比，圖靈引入了“可計算數(shù)（序列）”（computable numbers/sequence）概念，表示機器寫下的所有實例的計算結(jié)果，而將給定實例的計算結(jié)果置于此序列中，表達了實例與問題的“整體中個體”的關(guān)系，也就是說，“判定問題”包含在“判斷問題”中。

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

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

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

3，“可計算序列”，“計算機器”與“可計算問題”

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

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

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

-如果一臺機器打印兩類符號，第一類（稱為數(shù)字）全是0和1，其它被稱為第二類符號，則機器將被稱為“計算機器”。如果給機器裝置一條空白紙帶，讓它運動起來，從正確的初始m－格局出發(fā)，機器打印的第一類符號的子序列稱作機器計算的序列；在表達為二進制的十進制實數(shù)前放上小數(shù)點，稱作機器計算的數(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.）

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

-如果計算機器只寫下第一類有限數(shù)目的符號，被稱作“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的計算過程明確定義“可計算數(shù)（序列）”（Computable sequences/numbers）

-一個序列被說成“可計算的”，如果能夠通過一臺“circle-free machine”計算而得。一個數(shù)是“可計算的”，如果它與由“circle-free machine”計算的數(shù)只差一個整數(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)常說可計算序列，而不是可計算數(shù)。（We shall avoid confusion by speaking more often of computable sequences than of computable numbers.）

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

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

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

從圖靈的“可計算性”的角度，SAT表達為“判斷問題”:

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

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

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

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

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

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

1，“圖靈機”

判定問題：判定所有的自然數(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ù)。

圖靈機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都是“停機狀態(tài)”。

模擬M在輸入（n=2）的運行：

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

1 1 # # # …

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

q1 q2 q1 qY.

紙帶的變化：

# # 1 # # …

模擬M在輸入（n=3）的運行：

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

1 1 1 # # …

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

q1 q2 q1 q2 qN.

紙帶的變化：

# # # 0 # …

2，圖靈的“計算機器”

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

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

其可計算序列記為，α = 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ù))

。。。

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

q1, # , 0, R, q2

q2, # , # , R, q3

q3, # , 1, R, q4

q4,# , # , R, q1

模擬此機器的運行：

# # # # # # …

q1 q2 q3 q4 q1 q2 …

0 # 1 # 0 # …

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

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

q1, 1, #, R, q2

q2, 1, #, R, q1

q1, #, 1, R, q1

q2, #, 0, R, q1

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

模擬此“圖靈機”的運行：

開始的紙帶：

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

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

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

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

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

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

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

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

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

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

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

七，結(jié)語

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

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

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

- 基于“可計算序列”的NP問題。

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

- “圖靈機”完成對一個實例的計算而“停機”，“無限長的紙帶”被解釋為計算一個實例“不計時空開銷”；

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

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

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

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

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

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

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

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

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

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

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

責(zé)任編輯：haq