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

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

一，引言

二，NP定義溯源

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

1，NP的形式定義

2，分析NP的形式定義

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

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

1，Entscheidungsproblem溯源

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

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

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

五，案例研究：現有的“圖靈機” vs圖靈的“計算機器”

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

七，結語

一，引言

在現有的計算機理論中，P（Polynomial time）指“圖靈機在多項式時間可判定的問題類”，但是對NP（Nondeterministic Polynomial time），情況卻復雜得多，首先有一個教科書式的定義，“NP是不確定性圖靈機在多項式時間可判定的問題類”（NP is the class of problems decidable by Non-Deterministic Turing Machine (NDTM ) in polynomial time -定義1），后來又發展出一個更通俗化的定義，“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問題的前途進行了三次調查[3]，表明人們為尋找求解NP問題的多項式時間算法付出了巨大的努力，以求一舉解決P vs NP難題，但是迄今為止并沒有出現有價值的進展方向。

Hemaspaandra在介紹Gasarch的第二次調查時說：我希望在遙遠的未來，當人們讀到這四篇文章（指介紹P vs NP問題的四篇文章），可以幫助他們了解，在“P vs NP”還沒得到解決的黑暗年代里人們的思想狀態（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的認知上，表達為NP定義，關于NP的定義纏繞了計算機基本理論幾十年，比如，Scott Aaronson在博客“The Scientific Case for P≠NP”說：似乎有一個“看不見的電圍欄”把P問題與NP完全的問題區分開(there seems to be an "invisible electric fence separating the problems in P from the NP-complete ones) [5]。

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

二，NP定義溯源

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

定理1：如果一個符號串集合S被某種不確定性圖靈機在多項式時間內接受，那末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問題實例，神諭機“可解”，此“解”可由圖靈機多項式時間“驗證”。然而，由于神諭機不是構造性的機器模型，在現實中并不存在，為了將神諭機從NDTM中排除，學界遂將NDTM的計算行為解釋為“猜測＋驗證” [8]，即對于一個NP問題實例，NDTM在多項式時間“猜測”出一個候選解，并能在多項式時間“驗證”。經過這樣的解釋，NDTM就從“查詢機”變成了現在的“多選擇的NDTM”，即相對于在計算的下一步只有“唯一的選擇”的TM，NDTM可以有“多選擇” [9]。于是，得到NP的第二個流行定義：

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

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

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

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

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

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

1，NP的形式定義

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

- 令R為二進制字符串的關系；即，讓R為一組有序對(x,y)的集合，其中x和y是二進制字符串。如果存在確定性圖靈機在多項式時間內判定給定的(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.)

- 現在我們準備定義NP。語言L在NP中，當且僅當存在多項式可判定且多項式平衡的關系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滿足某種性質}，表達元素x與集合A的所屬關系，即“整體中個體”，而判斷x是否在A中，即判斷元素x是否具有性質G(x)。

從這個理解出發，SAT呈現出二個層次上的定義：

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

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

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

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

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

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

這也正是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問題的“可計算性”的直接肯定，而非論證，實例與問題的關系從“整體中的個體”變成了“個體即整體”，“判斷問題”因此被取消了，從而失去了揭示NP本質的可能性，暗含NP=P。下面我們從現有的“可計算性”觀念中追究更一般性的原因。

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

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

“圖靈機模型使用無限長紙帶作為其無限內存，有一個讀寫頭。最初，輸入字符串被放置紙帶上，紙帶的其他方格均為空白。機器將繼續計算，直到決定產生輸出為止。通過進入指定的接受和拒絕狀態來判斷是否接受和拒絕輸入，如果圖靈機不進入接受或拒絕狀態，則將永遠持續下去，永不停止。[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問題（任意實例）就沒有區別，這就是“判定問題”與“判斷問題”之間越界的等價關系的來源！

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

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

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

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

1，Entscheidungsproblem溯源

Entscheidungsproblem源于希爾伯特1900年所作的《數學問題》的著名講演，其中提出了數學理論中的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.

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

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

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

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

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

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

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

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

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

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

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

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

圖靈進一步區分Circular machine和Circle-free machine：

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

-一個序列被說成“可計算的”，如果能夠通過一臺“circle-free machine”計算而得。一個數是“可計算的”，如果它與由“circle-free machine”計算的數只差一個整數。（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.）

并且說：

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

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

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

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

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

-判斷問題：是否存在計算機器判定SAT的給定實例fn可滿足，這相當于計算序列α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的給定實例，是通過重復調用多項式時間驗證解的計算機器M而具有“指數時間復雜度”，所以“窮舉法”的本質就是計算機器M，而“窮舉法”的指數增長的計算開銷能否勝任SAT的實例規模的增長，即能否計算αL = G(f1)G(f2)G(f3)…G(fn)…成為了“問題”，換句話說，多項式時間驗證解的計算機器M對SAT問題是否具有可計算性成為了“問題”，是有問題：“SAT是窮舉法可計算的嗎？”

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

五，案例研究：現有的“圖靈機” vs圖靈的“計算機器”

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

1，“圖靈機”

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

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

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

圖靈機M1的規則表：

q1, 1, #, R, q2

q2, 1, #, R, q1

q1, #, 1, R, qY

q2, #, 0, R, qN

q1表示“初始狀態”，qYt表示“接受狀態”, qN表示“拒絕狀態”，qY與qN都是“停機狀態”。

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

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

1 1 # # # …

內態的變化：

q1 q2 q1 qY.

紙帶的變化：

# # 1 # # …

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

開始的紙帶放置任給的一個自然數：

1 1 1 # # …

內態的變化：

q1 q2 q1 q2 qN.

紙帶的變化：

# # # 0 # …

2，圖靈的“計算機器”

根據圖靈對“判斷問題”的表達：

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

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

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

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

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

。。。

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

q1, # , 0, R, q2

q2, # , # , R, q3

q3, # , 1, R, q4

q4,# , # , R, q1

模擬此機器的運行：

# # # # # # …

q1 q2 q3 q4 q1 q2 …

0 # 1 # 0 # …

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

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

q1, 1, #, R, q2

q2, 1, #, R, q1

q1, #, 1, R, q1

q2, #, 0, R, q1

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

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

開始的紙帶：

1 # 1 1 # 1 1 1 # …

內態的變化：

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

紙帶的變化：

# 0 # # 1 # # # 0 …

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

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

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

如上述分析，NP定義的本質是對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.

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

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

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

可見，在現有的“可計算性”理論中，存在著判斷“主體”的混淆，導致對個體與整體關系認知的混淆，暗中用“個體即整體”替代了“整體中個體”，這正是流行NP定義所隱藏的認知錯誤的來源，所謂“數學家的誤解” [15]。

七，結語

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

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

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

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

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

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

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

由此導致關于“可計算問題”的二種觀點：

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

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

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

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

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

- 為什么“可計算序列（數）”的概念從現有的計算理論中消失了？

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

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

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

責任編輯：haq