動機
給機器更多時間,應當能讓它解決更多問題,但證明必須面對一個障礙:模擬器在詮釋被模擬的機器時,本身也要花費時間。若恰好使用某部所謂更快的機器所容許的時間來做對角化,這筆模擬開銷就可能耗盡全部預算。確定性時間層級定理留出一個對數量級的間隙,其大小足以吸收這筆開銷,然後再翻轉被模擬機器的答案。
我們把所用的模擬事實作為背景陳述,並透過明確的填充與量詞來證明對角化論證。
定義
對函數 , 是指能被確定性多帶圖靈(Turing)機在 時間內判定的語言類。此處稱函數 是時間可構造的,若存在一部確定性時鐘機器,給定長度為 的一元輸入,恰好運行 步後停機。我們假設對所有充分大的 有 ;有限個較短的長度可以單獨處理。
我們所用的標準通用模擬事實如下:存在一部確定性通用機器 ,使得對每一部固定的確定性多帶機器 ,在長度為 的輸入 上模擬 的 步,至多需要 的
步,其中包括對 的有限編碼的存取。常數依賴於 ,而不依賴於 或 。對數因子反映了對固定條數紙帶的高效模擬;我們直接使用這一標準結果,此處不證明紙帶模擬。模擬必須區分接受與拒絕,並持續進行,直到被模擬的機器停機或外部時鐘到期。
若存在某部機器在時間 內判定一個語言,而 滿足 ,則該語言屬於 。這是對所有此類界取聯集,而不是單一固定常數倍的時間類。
定理
定理 4.3.1
(帶時鐘的時間層級定理)
對滿足上述增長假設的時間可構造函數 ,存在一個屬於 的語言,它不屬於 。因此後一個類是 的真子類。
這一陳述是一個保守的版本,明確留出了讀入輸入所需的餘量。它並不聲稱任意一對僅相差常數倍的界都能給出分離,也沒有消除對數量級的模擬代價。
推論 4.3.2
(多項式時間預算的嚴格分離)
對固定整數 ,確定性多帶類滿足 。標準的多項式時鐘應理解為至多相差無關緊要的常數與低階時鐘約定;這些約定給出同一個 類。該結果分離的是這些類中的語言,而不是為某個熟悉的具體問題指定精確的運行時間。
證明
固定確定性機器的一個有效枚舉 。如下設計對角判定機 ,其輸入為長度為 的二進制串 。若 具有形式 ,則把其開頭的一段詮釋為索引 ;後綴 是填充,不改變所選中的機器。不含零的輸入可以指定一個固定答案。掃描輸入,並在 時間內在另一條紙帶上寫出一個真實的一元串 。在該紙帶上運行 時鐘,同時用 在整個輸入 上模擬 。若模擬在時鐘到期之前停機,則輸出相反的答案。若時鐘先到期,則接受。
把索引解碼放進時鐘之內
有效枚舉未必能隨 快速給出第 部機器的描述。因此,統一的模擬過程必須在時鐘啟動之後,才開始解碼或枚舉該描述。每一步解碼、複製和模擬都計入帶時鐘的過程。若輸入選中了一個極其龐大或不便處理的描述,它可能在機器尚未初始化時就已超時;按約定給出的超時答案,仍然是一個完全有效的判定。
對於一個固定的候選索引 ,解碼其有限描述需要固定的有限步數 。矛盾論證可以把這筆開銷吸收進該候選機器的模擬常數中。然而,在所有可能的索引與任意輸入之上,我們並不需要 的一致上界:實際完成的工作量由外部時鐘限定。因此,該證明不會不慎將 的整體運行時間界乘上一個隨輸入而變、沒有上界的描述常數。
時鐘和詮釋器都是固定的多帶機器。一部組合機器可以利用分開的紙帶區域,以及二者控制狀態的有限乘積,輪流給每個部分執行一步。這樣的一輪只花費固定的步數;詮釋器所做的長時間掃描或代碼構造則消耗許多輪。只有一元輸入帶和少量初始標記在計時開始前準備好,耗時 。特別地,我們從不預先寫下 個時鐘標記,也不假定模擬的紙帶讀寫頭移動其實現代價為零。
模擬與時鐘輪流進行,所以 的實際時間為 ,其中包括檢查輸入前綴、寫出一元帶以及初始化模擬。初始的一元帶有 個單元格;沒有預先建立任何大小為 的物件。由於時鐘會停機,這一確定性計算的每個分支都會停機。在分配的模擬時間內拒絕的機器同樣會被翻轉為接受;超時不會被誤當作被模擬語言的非成員資格的證明。
針對單一固定候選機器利用漸近間隙
證明
(與單一固定候選機器的矛盾)
假設為了導出矛盾,某部確定性機器 在時間 內判定 的語言。對這個固定的 ,通用模擬的界為
確實,由增長假設有 ,並且最終有 ,所以 。對每個充分大的 ,任取一個以 開頭、長度為 的輸入;填充使得這樣的輸入在任意大的長度上都存在。在該輸入上,模擬在時鐘之內完成。於是由 的定義得 ,這與 判定同一語言的假設相矛盾。
對這個固定的索引,索引解碼的代價 同樣是 ,因此不會改變上述結論。若假想的判定機的運行時間界是 而不是恰好 ,其常數同樣可以被吸收:乘以一個固定常數不會破壞小 o 界。輸入長度的最終閾值只在選定該候選機器及其常數之後才選取。證明並不需要一個對所有機器索引同時有效的單一閾值。
證明透視
為何先固定候選機器,再選取長度門檻
唯一不尋常的一步是選擇的次序:先固定候選機器 ,然後才選取長度門檻。這個次序使與機器相關的常數 與 得以被吸收:對每個固定的 , 都成立,儘管沒有單一的門檻對所有 同時有效。填充是第二項要素:它使索引 成為每個足夠大長度的輸入之前綴,漸近界因而真正派得上用場。增長假設 支付讀入輸入的代價,而 小 o 因子 支付通用模擬的代價。論證以直接的分歧作結:在某個填充後的輸入上,模擬在時鐘之內完成, 輸出與 相反的答案。若沒有這個間隙,這一步便會失敗。對於 ,模擬代價 對大的 約為 ,只要 便超過時鐘,因此時鐘可能先到期, 便不一定與 不同。
請注意, 從不需要計算 ,不需要估計競爭機器的漸近複雜度,也不需要識別哪些候選機器滿足小 o 條件。它對每個輸入都遵循同一條有限的時鐘規則。較小的界這一假設只出現在外部的矛盾論證中,在那裏它保證所謂更快的判定機最終會及時完成其模擬,從而被矛盾所否定。若讓算法去檢驗這一假設,就會引入一個完全不同且沒有依據的可計算性要求。
至於包含關係:每個滿足 的函數 最終都是 ,而有限個較小的輸入可以被吸收進常數。對角語言屬於較大的類,卻不屬於較小的類,所以該包含關係是真包含。
增長條件只是最終成立的。選取一個固定長度,使其之後條件成立,並在更短的輸入上用一張有限表任意定義對角語言。這張表是單一有限機器描述的一部分,即使它的常數規模很大;它並不給出機器在無窮多個長度上的答案。帶填充的矛盾論證所用的長度,同時超過這個固定的截止點和所選候選機器的收斂閾值,因此這張表不會產生干擾。
時間可構造性同樣是操作意義上的要求。僅僅寫出某個設想截止時間的二進制數值,並不能提供本證明所用的時鐘。我們假設存在一部真實的機器,它的步驟在所述模型下實現這一截止時間。這個假設使每次超時都是有效的,使每個輸入都是可判定的;它並不是要求對角機還要能對作為數據給出的任意函數識別該條件。
證明
(多項式時鐘下的比值)
對於多項式推論,取階為 的時鐘。對於階為 的候選界,相關的比值是 的常數倍,它趨於零。例如,代入 ,收斂性化為 。因此層級語言不在任何 的常數倍之內,而其構造仍然落在 的常數倍之內。普通的包含關係也直接成立,只需容許較小預算的判定機留有未使用的額外時間。
這是語言類之間的嚴格分離,並不是聲稱所有階為 的算法都需要那麼多時間。較大類中的許多語言本來就有更快的算法。該構造也沒有給出為任意給定程式尋找緊下界的統一方法:它的單一對角語言被刻意設計為,在每個足夠快的候選機器的填充輸入上與該候選機器不一致。
反例模式
一半的時間並不是較小的類
斷言:由於對每個 都有 ,該定理應給出一個屬於 而不屬於 的語言。這是錯誤的。按定義, 容許 步,而 ,所以兩個類相等。定理的假設在此並不成立:對 與 ,比值 趨向無窮大,而不是趨向零。上述證明需要至少相差一個對數因子的間隙,而不是僅僅數值較小。
例題詳解
例題 4.3.3
(多項式時間界)
取 (),在小的 處採用無關緊要的時間可構造約定。該定理給出一個語言,它可在 時間內判定,卻不能在 時間內判定:事實上 。這一分離涉及的是所選模型下的確定性時間類,並不意味著某個熟悉的自然問題恰好具有這樣的複雜度。
例題 4.3.4
(為甚麼填充很重要)
設目標機器是 ,由前綴 表示。在每個足夠大的長度上都有以該前綴開頭的串,例如該前綴後面接上所需數量的零。模擬常數 可能極其巨大,但小 o 的收斂最終會壓過任何固定的 。若 只有一個短的編碼,我們就無法在任意大的輸入長度上援引漸近的運行時間界。
例題 4.3.5
(一個對數因子與兩個對數因子)
設在大的長度上 。界 滿足 ,所以該定理排除了以此為界的判定機去判定所構造的語言。相反, 的比值為一,不在本陳述的涵蓋範圍內。它的模擬代價可能仍然是 的一個固定比例,再帶上依賴於候選機器的因子,對這個時鐘而言就太大了。因此,僅僅在數值上小於 ,並不是這裏所證明的假設。在充分大的長度上,取整約定(無條件捨去或無條件進位)都不會改變這兩個比較。
常見錯誤
對角機必須在比較雙方答案的同一個完整輸入上模擬候選機器。另外,僅僅說「 小於 」是不夠的:證明必須計入通用模擬器的 因子以及處理輸入的代價。最後,該定理給出的是一個專門構造的語言;它既沒有證明 ,也沒有給出某個具名的 NP 完全問題的無條件下界。
總結
帶時鐘的模擬使對角化不會無限運行下去。填充提供了任意長的、指名每個固定候選機器的輸入,而小 o 的間隙吸收了該機器固定的模擬常數。在所述的可構造性與模擬假設之下,這些要素在確定性時間內部造出了無條件的嚴格層級。
練習
快速檢查
(解釋為甚麼 。)
解答 · 答案
比值為 ,它趨於零。
快速檢查
(對 ,利用該定理分離 與 。)
解答 · 答案
由於 ,對角語言屬於 ,而不屬於 。標準的多項式時鐘滿足可構造性條件。
快速檢查
(當被模擬的機器在時鐘到期之前拒絕時, 輸出甚麼?若它在截止時間仍未停機呢?)
解答 · 答案
兩種情形下它都接受:第一種情形透過翻轉拒絕,第二種情形依據約定的超時規則。這兩種情形在證明中扮演不同的邏輯角色。
快速檢查
(為甚麼證明容許通用模擬的常數依賴於 ?)
解答 · 答案
一旦固定了某個候選機器 , 就與輸入長度無關。儘管有這個固定常數,小 o 的收斂仍使得在所有充分大的填充輸入上,開銷小於時鐘。
快速檢查
(該定理是否證明了 SAT 不能在二次時間內求解?請解釋。)
解答 · 答案
不能。所構造的分離語言不必是 SAT,甚至不必屬於 NP。該定理給出的是時間類的分離,而不是對較大類中每個具體問題的下界。