複雜度理論探討的是資源如何隨輸入長度增長,而不是某部手提電腦在某個輸入上需時多久。在度量一個計算之前,我們必須指明甚麼算是輸入、答案與一個步驟。一個精確的模型亦會揭示一個更根本的限制:有些判定問題根本沒有任何算法。
為何先要談資源與模型
像「這個算法很快」這樣的陳述,在以下三件事未確定之前並無數學內容:算法所接收的對象、它可以執行的運算,以及被計算的量。複雜度理論把這些選擇一次定下,使不同問題的陳述可以互相比較,並使有關所有算法的定理成為可能。形如「沒有算法能做到 X」的定理,是對任何人可能寫出的每一個程式作量化。只有當「算法」已獲得足夠精確、足以進行推理的定義,這樣的陳述才有意義。
本單元有兩個目標及一篇續篇。第一,定義判定問題、確定性計算與時間界限,並確切了解為何輸入的編碼屬於問題的一部分。第二,以兩個不同的論證證明不可判定語言存在:一個是計數論證,顯示它們數量眾多;另一個是對角構造,給出一個具體的例子。續篇把對角想法用於可計算的時間截斷,並說明證明層級定理還需要哪些工作。
關於此處所證明的內容,有一點說明。除非某個陳述被明確標示為未證明的依賴,否則本單元中所有標示為定理或命題的內容均有完整證明。標準機器模型之間具有多項式額外開銷的模擬,以及試除例題中的 Bertrand 公設,均不加證明地使用。
模型與判定
定義 4.1.1
(語言與確定性計算)
固定一個有限字母表,例如 。語言 是有限字串的一個集合。若確定性圖靈(Turing)機在每個輸入上都會停機,並且恰好接受 中的字串,則稱它判定 。它在某個輸入上的時間是直至停機所需的步數;它在長度 的最壞情況時間,是所有長度為 的輸入上的最大值。類別 包含可由確定性機器在以輸入長度的多項式為界的時間內判定的語言。
編碼是問題的一部分。例如,二進位整數 的長度約為 ,因此一個需時 步的算法,未必在輸入長度上屬多項式時間。合理的確定性機器模型在時間上可以多項式額外開銷互相模擬,所以類別 在標準的模型轉換下是穩健的;此模擬事實在此不加證明地使用。然而,精確的運行時間指數仍可能取決於模型。
判定問題就一個輸入提出是或否的問題,而語言則把該問題包裝成答案為「是」的輸入所成的集合。就本單元而言,限於是或否的答案不會損失任何東西。計算一個函數可以改寫為判定由輸入與輸出所成之對的語言,而我們所研究的困難現象在這個最簡單的設定中已經出現。
還需要兩個概念。若一台機器接受 的每個字串,並且不接受 以外的任何字串,則稱它辨識語言 。對於 以外的字串,它可以拒絕或永遠運行下去。每個判定器都是辨識器,但反過來並不成立,停機問題將會顯示這一點。若某台機器判定一個語言,則該語言是可判定的;若某台機器辨識它,則該語言是可辨識的。
時間界限與類別 P
定義 4.1.2
(在時間界限內判定)
設 為一個函數。若確定性圖靈機判定 ,並且對每個 及每個長度為 的輸入 ,它至多在 步後停機,則稱它在時間 內判定 。類別 由以下語言組成:存在一台在每個輸入上均停機的判定機器及常數 ,使得對所有充分大的輸入長度,其運行步數至多為 。於是 ,這與上文的定義一致,因為當 時,多項式必以某些 與 的 為界。
最壞情況的約定至關重要。一台機器即使在大多數輸入上極快,但在每個長度的某一個輸入上需要 步,其最壞情況時間便是 ,而這正是定義所記錄的量。平均情況的表現屬於另一個課題,此處不作度量。
多項式時間之所以佔有核心地位,部分原因在於它對複合封閉。若一個多項式時間的程序為另一個程序準備輸入,則兩者的組合仍是多項式時間。以下命題使此點精確化,其證明用到一個容易被忽略的觀察:機器所能寫下的符號數目不能多於它的步數。
命題 4.1.3
(多項式預處理保持 P)
設 為從字串到字串的函數,可由確定性圖靈機在長度 的輸入上以至多 的時間計算;設 在長度 的輸入上以至多 的時間被判定,其中 與 為係數非負的多項式。則 可在多項式時間內判定;因此 。
證明
(複合界限的證明)
對於長度為 的輸入 ,先運行 的機器。它在 步內停機。每一步至多只能訪問一個新的帶格,而輸入已佔用 個格,所以至多訪問過 個格,輸出 的長度 。然後在 上運行 的判定器,其運行時間至多為 。由於 的係數非負,它是不減的,所以 。機器恰好在 時接受。在標準的單帶模型上,以多項式步數整理並定位輸出,例如至多為 的某個常數倍。這兩個階段與此轉移成本有一個多項式界限。
若沒有輸出長度的觀察,對粗心的讀者而言,此命題按所述會是錯誤的。一個快速但產生巨大輸出的第一階段,會令第二階段變得昂貴。證明顯示這不可能發生:輸出長度受運行時間所控制。
編碼與輸入長度
本節的核心提醒是:同一個程序可以是高效或低效,僅取決於輸入如何書寫。上文已用過的下列例子是典型範例。
例題 4.1.4
(輸入大小改變界限)
對正整數 重複遞減需要 次迭代。若 以 個位元的二進位書寫,則 可大至 ;因此這個程序在 上的最壞情況迭代次數是指數的。以一進位輸入 時,同樣的次數相對於輸入長度是線性的。這些是不同的編碼,因此是不同的複雜度陳述。
下一個例子對一個看似無害的程序,即試除法,作出精確的計算。
例題 4.1.5
(試除法在位元長度上是指數的)
考慮這樣的程序:給定二進位整數 ,對每個滿足 的 進行測試,若有某個 整除 ,便宣告 為合數。取 ,它有 個位元。由於 而 ,我們得 。所以只要沒有較早找到因數,該程序便測試 個除數。(這個特定的 是質數,所以全部 次測試都會執行。)
對一般的 ,假設首位元為 ,使 。則 ,而質數輸入迫使至少有 次除法。對 ,此下界為 ,與上面的精確次數一致。對 ,下界為 ,超過十億次除法。由 Bertrand 公設(此處不加證明地使用),對每個 都存在 位元的質數;因此最壞情況的除法次數是 。現在把編碼改為一進位,使輸入長度為 。除法次數至多為 ,每次的成本是 的多項式,所以同一程序在 上以多項式時間運行。算法沒有改變;改變的是輸入大小的度量。(已知有一個定理指出,在二進位編碼下質數判定存在多項式時間算法,但那是一個不同而且巧妙得多的算法,本單元的內容並不依賴它。)
教訓是:「在數字上為多項式」與「在數字的長度上為多項式」是不同的概念,而複雜度理論預設指的是後者。成本在數值上為多項式、但在位元長度上為指數的程序,有時稱為偽多項式,每當輸入中出現整數時,它們就會再次出現。
例題 4.1.6
(同一數值的兩種編碼)
整數 的二進位表示是 ,因此二進位輸入長度為四。將它不斷減一直至零的循環執行十三次;由 得 。一進位輸入則是十三個一構成的字串,同樣的十三次迭代對該輸入長度是線性的。算術數值沒有改變,但複雜度陳述中的規模參數不同。一個例子不能證明漸近界,卻能說明最壞情況分析中應讓哪個量變化。
計數:大部分語言都是不可判定的
在給出一個明確的不可判定語言之前,我們先說明不可判定語言必然存在,原因純粹是數量上的:語言太多,而機器太少。
命題 4.1.7
(不可判定語言存在)
圖靈機只有可數多個,因此 上的可判定語言也只有可數多個。 上所有語言所成的集合是不可數的。因此 上存在某個語言是不可判定的。
證明
(以計數與 Cantor 對角化證明)
每台圖靈機都有一個有限的描述(它的狀態、字母表與轉移表),可以寫成固定有限字母表上的一個有限字串。有限字母表上的有限字串所成之集是可數的:依長度遞增列出,同一長度內依字母順序排列。所以機器可以列為 ,而每台機器至多判定一個語言。因此可判定語言都包含在一個列表 之中(對於不判定任何語言的機器,重複一個固定的可判定語言,例如空集)。
現在以同樣的先按長度、再按字母順序,把所有二進位字串列為 ,並定義
對每個 ,語言 與 在字串 上不一致,所以 。因此 不在列表的任何位置,尤其是它不可判定。同一論證應用於任何所提出的語言列表,都顯示沒有列表包含所有語言,所以語言所成之集是不可數的。
這個論證純粹是存在性證明。它沒有說明哪些語言是不可判定的,並且正確地暗示:「典型」的語言是不可判定的,而可判定的語言才是例外。它亦預示了下一節的機制:字串 被用來向第 台機器查詢關於它自身的問題,然後把答案反轉。
一個不可判定問題
定理 4.1.8
(停機語言是不可判定的)
設 ,並使用機器與輸入的有效編碼。沒有確定性圖靈機判定 。
證明
(對角證明)
假設存在判定器 。構造一台機器 :在輸入編碼 時,它在 上運行 。若 指 在其自身的編碼上停機,則 永遠循環;否則 停機。現在在 上運行 。若它停機,則來自 的正確答案迫使它循環;若它循環,則正確答案迫使它停機。兩種情況都與所假設的 的正確性矛盾。
證明透視
自我指涉用到了甚麼,又忽略了甚麼
論證依靠三件事。第一,假設 是判定器,所以它在每個輸入上都停機, 是一部有明確定義的機器;全域性(totality)正是在這裏被用上。第二,編碼是有效的: 可以機械地由 計算出 。第三,唯一不顯而易見的一步,是把 自己的描述輸入給 ,使 對 的回答,正好是 被構造來反駁的內容: 在 上停機,當且僅當 報告 在 上不停機。由於 的報告按假設是正確的,矛盾便告成立;其餘每一步都是機械的構造,所以唯一可能出錯的,就是 的存在。若 只是辨識器,論證便毫無結果:當 在 上不停機時, 自己也可能不停機,於是 同樣不停機,並無矛盾,這與 可被辨識是一致的。
這個矛盾並不表示沒有任何特定的機器與輸入之對可以被分析。它表示的是:沒有一個全域的算法能正確地解決每一個已編碼的對。 的辨識器確實存在:模擬 在 上的運行,若它停機便接受,但這個辨識器在非成員上會永遠運行。判定要求在是的實例與否的實例上都停機。
反例模式
模擬器不是判定器
斷言:模擬 在 上的運行、並在模擬停機時接受的機器 能判定 ,因為只要它作出回答,答案就是正確的。反例:令 為只有一個狀態的機器,其唯一的轉移是在每個符號(包括空白符)上把讀寫頭向右移一格,並且沒有停機狀態。在輸入 上,模擬永遠不會完成,所以 既不接受也不拒絕。這個對不屬於 ,判定器必須停機並拒絕它。因此 辨識 ,卻沒有判定它。補救的辦法不是更巧妙的模擬器:上述定理顯示,沒有任何機器能在所有的對上正確地停機。
常見錯誤
(不可判定與昂貴)
指數時間的算法仍然是在每個輸入上都會停機的算法。不可判定排除了每一個判定器,不論時間界限為何;它不僅僅是在聲稱最佳的算法很慢。
概念視角結構
可判定即兩側皆可辨識
一個語言可判定,當且僅當它和它的補集都可辨識:讓兩個辨識器交替運行、每次各走一步,恰有一個最終會接受。因此, 可辨識但不可判定,它的補集便不可辨識。
練習與解答
快速檢查
(某程序在 的二進位編碼上運行 次迭代。請以位元長度 的函數給出最壞情況的界限。)
解答 · 答案
由於 ,迭代次數少於 ;接近 的輸入顯示最壞情況是指數的。
快速檢查
(解釋為何對 在 上的模擬辨識但並不判定 。)
解答 · 答案
若 停機,模擬最終會觀察到這一點並接受。若 永不停機,模擬永遠不會完成,所以它不符合判定器必須在每個輸入上停機的要求。
快速檢查
(某試除程序對一個有 個位元且首位元為 的二進位整數 ,測試所有滿足 的 。證明只要 在該範圍內沒有因數,便至少執行 次除法。)
解答 · 答案
首位元為 給出 ,所以 ,而 。被測試的除數為 ,其數目為 。若不存在因數,則這些測試每一次都會執行。
快速檢查
(函數 在時間 內被計算,而語言 在長度 的輸入上於時間 內被判定。請給出判定 的多項式界限,並指出其次數與首項係數。)
解答 · 答案
輸出長度至多為 ,所以第二階段至多需時 步,再加上多項式的轉移成本 ,便得到一個多項式界限。該界限的次數為 ,首項係數為 ,因為轉移項的次數較低。
快速檢查
(長度至多為 的二進位字串所成之集中,包含多少個不同的語言?一般而言,長度至多為 的二進位字串所成之集中包含多少個?)
解答 · 答案
長度至多為 的二進位字串有 個(空字串、長度為一的兩個、長度為二的四個),而每個語言都是這些字串的子集,所以有 個語言。一般而言,長度至多為 的字串有 個,因此語言有 個。
續篇《歸約、辨識器與有界時間對角化》繼續討論歸約和後面的對角構造。