為何計算模型之間需要證明
描述驗證者時,用一條紙帶存輸入、一條存證書、另一條做草稿很方便;構造計算表時,卻可能要求只有一條紙帶和一個讀寫頭。兩種描述之間必須有數學上的橋樑:模擬器既要保留答案,也要把額外耗時控制在所聲稱的資源範圍內。
本節為固定有限條普通圖靈(Turing)機紙帶建立這座橋樑。我們寫出表示方式、證明不變量,並計算實際掃描耗時。這個初等構造證明多項式時間的穩健性,但不證明確定性時間層級章節所使用的更精細的通用模擬界。
兩種模型
定義 4.2.1
(多帶圖靈機)
固定正整數 和有限紙帶字母表 ,其中包含輸入符號 與空白符。 帶圖靈機有一個有限控制器,以及 條以整數為座標的雙向無限紙帶。一次轉移讀取各頭下的 個符號,改變狀態,在每條帶上寫一個符號,並把各頭移動 中的一個距離。、字母表和轉移表屬於固定機器,不是輸入的一部分。
對於 ,第一條帶在座標 存放 ,其餘位置為空白;其他帶完全空白。所有頭從座標零出發, 時也一樣。接受和拒絕狀態都是停機狀態。時間以轉移次數計, 限制每個長度為 的輸入上的耗時。
模擬器只有一條雙向無限紙帶和一個頭,可以使用比 更大的固定有限字母表。字母表大小只依賴被模擬機器。本節把輸入放在計入使用範圍的紙帶上,只討論時間;它不證明帶有獨立免費輸入帶的對數工作空間模擬。
把虛擬紙帶存成多軌記錄
定義 4.2.2
(虛擬紙帶的多軌表示)
每個被表示的座標 對應一個物理格,其記錄含有 個虛擬紙帶符號,以及每軌各一個舊頭標記和新頭標記。區間兩端以分隔符界定。被模擬的控制狀態保存在模擬器的有限控制器中。
每次虛擬轉移開始時,保持以下不變量:
- 每軌恰有一個舊標記,位於該虛擬頭的當前位置;所有新標記均為空。
- 區間內記錄等於當前虛擬紙帶內容,區間外所有虛擬格均為空白。
- 各虛擬頭均在區間內,有限控制器保存正確的被模擬狀態。
不含分隔符時, 種記錄就足夠。因此一條記錄可作為固定字母表中的一個符號。這裏同時保存 個符號是合法的,因為 固定;我們沒有假設可用單位時間處理隨輸入增長的紙帶數。
初始化掃描輸入,把每個輸入符號改寫成記錄,其他軌填空白。空輸入則在座標零建立空白記錄。在各軌的座標零放舊標記,兩端各補一個空白記錄,再在外側放分隔符,耗時 。記 ,初始區間可取 ,共有 條記錄。
例題 4.2.3
(兩個虛擬頭可以位於同一個物理格)
設 ,第一帶存 ,第二帶為空。在座標零,記錄的符號對為 ,兩個舊標記都設為一。它們是同一記錄中的不同位,表示兩個虛擬頭。唯一的物理頭一次讀出整條記錄。之後虛擬頭可以分開,物理頭便在不同時刻訪問它們所在的記錄。
用固定次數的掃描完成一次轉移
先在區間兩端各增加一條空白記錄,並把兩個分隔符各向外移一格,原端點記錄不變。尋找另一端所需的遍歷也計入掃描耗時;固定次數的遍歷足夠完成擴展。因此,即使舊頭在端點,下一次轉移的目標格也已被表示。
接著從左向右掃描。第 軌唯一的舊標記給出其讀取符號 。把 存在有限控制器中,由它與當前狀態確定轉移:下一狀態、各軌寫入符號及移動方向。這些數據對固定機器都只有常數大小。
向回掃描並執行更新。遇到第 軌的舊標記時,在該軌寫規定符號並清除舊標記,再按方向在本格或相鄰格放第 軌的新標記。物理頭可短暫移動到相鄰格、修改相應欄位,然後返回,繼續主掃描;經過其他欄位時保持其值。若同一格有多軌舊標記,就按固定軌次序處理。
更新只識別舊標記。新目標格可能已掃描,也可能尚未掃描,這不會改變本次要處理的舊標記集合。訪問鄰格時,不遞歸調用更新過程;有限控制器記住自己正在完成局部往返,返回後才恢復主掃描。舊標記總共只有 個,故這樣的往返至多 次。
最後再掃描整個區間,把所有新標記改為舊標記,存入下一狀態,並回到規定邊界準備下一輪。完成 輪後,區間可為 ,含 條記錄。無論虛擬頭如何移動,每輪只增加兩條記錄。
定理 4.2.4
(模擬不變量的保持)
每輪結束後,記錄與所存狀態恰好編碼原機器執行一次轉移後的組態。因此模擬器與原計算的接受、拒絕結果一致。
證明
(對輪數作歸納)
初始化滿足不變量。假設某輪開始前成立,擴展區間只添空白,與原區間外的虛擬內容一致。收集掃描讀到準確的舊符號元組,所以選中原機器的同一轉移。對每軌,更新只改動舊頭所讀的符號,並在指定目標恰好放一個新標記,其他符號保持原值。新標記不觸發更新,故不會把一次轉移執行兩次。清理後,各軌又恰有一個舊標記,新欄位全空,所存下一狀態也正確。對輪數歸納即得結論。遇到被模擬停機狀態就結束;初始狀態已停機的情形,可在初始化後識別。
證明透視
舊標記與新標記如何支撐歸納
除了更新規則之外,歸納還用到三項事實。收集掃描在任何寫入之前結束,所以轉移只由舊組態選出;這就是「選中原機器的同一轉移」的意思。寫入只產生新標記,而更新掃描只對舊標記作出反應,所以不論目標格相對於掃描處在哪一側,都不會有任何東西被執行兩次。清理只是重新命名角色,而不是搬動數據,從而恢復不變量。兩端各添加的緩衝記錄,使不變量的第 3 條在頭向外移動一步後仍然成立; 固定,則使被掃描符號的元組可以存放在有限控制器之中。若取消新舊標記的區分,下面例子中的失敗便會出現。
下面的例子說明,把兩組標記欄位分開,排除了甚麼問題。
反例模式
只有一種頭標記為何危險
設更新從左向右,虛擬規則使頭右移。如果清除座標零的標記後,立即在座標一放普通頭標記,那麼下一次掃描到座標一時,可能再次應用規則。一次虛擬轉移便使頭移動兩次,甚至一直重複到邊界。把掃描方向反過來也不能普遍解決,因為機器也能左移。分開的舊、新欄位用同一個不變量處理兩個方向。
計算物理步驟,而不是虛擬指令
定理 4.2.5
(平方量級的模擬開銷)
對每台固定的確定性 帶機器,若其耗時不超過 ,則上述確定性單帶模擬器耗時
若 ,此界為 。隱含常數可以依賴固定機器,包括 和其字母表。
證明
(累計所有輪次的耗時)
第 輪開始前已模擬 步。計入新緩衝格,區間有 條記錄。每輪掃描次數固定,局部常數距離往返至多 次,每個記錄的處理也是常數時間,所以該輪耗時 。原計算若實際執行 步,初始化及各輪總耗時至多
從而得到定理中的界。 時求和為空,但初始化仍需 。模擬器無須知道 或計算時鐘:它反覆模擬,直到原機器停機;時間界用於外部分析。
例題 4.2.6
(多項式界仍然是多項式)
一個固定三帶驗證者在總編碼長度為 的實例與證書上,最多執行 次轉移。單帶模擬耗時 。之後的單帶計算表構造可採用這個更大的多項式界,不能仍把原先的三次截止時間原封不動地套在模擬器上。
例題 4.2.7
(立即停機也要支付本構造的初始化成本)
一台立即拒絕所有輸入的機器有 。這裏的模擬器先掃描、編碼輸入,再報告拒絕,需要 ,符合一般界。若直接套 就會得到無意義的零界,因為其前提 不成立。專門優化當然可以省去掃描,但那不是已給出的構造。
非確定性與多項式類
對非確定性機器,時間界必須限制每條分支。收集掃描符號後,模擬器非確定地選擇原機器的一條可用轉移;其餘掃描、記錄和清理都確定執行。沒有可用轉移的死端拒絕,除非它已經是接受停機。對每個選擇序列,上述不變量分別成立,所以模擬器有接受分支,當且僅當原機器有接受分支;所有分支都滿足同一開銷界。無需猜測紙帶內容或頭位置。
推論 4.2.8
(固定紙帶數給出相同的 P 與 NP)
把一條紙帶改為任意固定有限條紙帶,不改變確定性多項式時間可判定的語言集合。在所有分支均有多項式時鐘的非確定性模型中,也不改變相應語言集合。
證明
(化為單帶情形)
單帶機可直接當作忽略其餘紙帶的多帶機。反向則把任意多項式界擴大成仍為多項式且滿足 的界,模擬只會再得到另一個多項式。逐分支論證給出非確定性結論。同理,證書編碼長度為多項式的確定性多帶驗證者,可改成單帶多項式驗證者,且接受的證書集合不變;時間始終按實際編碼長度計算。
常見錯誤
常見錯誤
(多項式穩健性不等於保留指數)
本結果保留多項式時間歸屬,不保留精確指數。它不證明兩種模型的線性或平方時間類相同,不給出時間層級論證所需的 通用模擬,也不保留對數空間。
常見錯誤
(紙帶數必須保持固定)
若 隨輸入長度增長,記錄不再來自同一個固定有限字母表,必須另建明確計費的模型。
練習
快速檢查
(若 且 ,不含分隔符時有多少種符號與標記記錄?為何可以使用它們?)
解答 · 答案
符號對有 種,四個標記位有 種,共 種。它只依賴固定機器,因此可放進一個固定有限字母表,不隨輸入增長。
快速檢查
(長度為四的輸入模擬七步後,上述表示可使用甚麼區間,共多少記錄?)
解答 · 答案
,區間為 ,共有 條記錄,與 一致。
快速檢查
(某頭左移到主更新掃描已經過的記錄,為何仍能正確表示其新位置?)
解答 · 答案
局部往返在那裏設定新標記後返回。主更新掃描不必重訪;後面的清理掃描經過全區間,把新標記改成舊標記。該軌的格中符號僅在它原本就是舊頭所讀的格時改變。
快速檢查
(為何必須在任何虛擬寫入前先收集全部讀取符號?)
解答 · 答案
原機器的一次轉移同時讀舊符號元組。若用部分已更新資訊選擇轉移,就可能讀到不同元組並選錯規則。先收集使讀舊組態與寫新組態分離。
快速檢查
(固定多帶算法耗時 ,本構造給出甚麼上界?是否也證明對應下界?)
解答 · 答案
先把界擴大到至少 ,再平方,對 得 ; 另取有限約定。這只是某個模擬器的上界,既不是原語言的時間下界,也不證明模擬最優。
快速檢查
(為何只限制接受分支的長度,不足以推出這裏的非確定性耗時結論?)
解答 · 答案
拒絕分支可能任意長,甚至不停機,模擬器沿著該分支也就沒有多項式時間保證。標準非確定性多項式時間模型對每條分支施加時鐘;存在接受分支是另一個條件。
快速檢查
(驗證者讀入長度 的編碼對,其中 為多項式,耗時 。證明單帶模擬對 仍為多項式。)
解答 · 答案
對 為多項式。擴大原時間界使其支配 ,模擬耗時為 ,故對 仍為多項式;不變量保證接受證書集合不變。
快速檢查
(本證明能否替代精細時間層級定理中的對數開銷通用模擬引理?指出缺少甚麼。)
解答 · 答案
不能。這裏對每台固定機器,在時間支配輸入長度時給出平方界。精細層級證明可能需要只增加對數因子的通用模擬器,還須控制機器描述的處理成本;這兩個更強結論都未在此建立。