合理的編碼（reasonable encoding）

在機器能咀嚼一張圖、一個數字或一個文法之前，這個物件必須被寫成一串符號，因為機器在紙帶上看到的就只有這些。把同一個物件寫下來的方法有很多種，而這個選擇並非無關緊要。合理的編碼是對大小誠實的那種：它不會偷偷把輸入吹大、或以扭曲問題難度的方式把它縮小。它就是我們用來量 n 的那把公認的尺。

經典的陷阱是把數字寫成一進位（unary）。用二進位編碼數字 12 約需 4 個符號（1100）；用一進位則要 12 個符號（111111111111），一百萬就要一百萬個符號。所以一進位編碼會讓輸入大小像數值 N 本身那樣成長，而非像 log N，這純粹靠灌水，就能在紙面上把一個指數時間方法變成「多項式時間」方法。我們排除一進位：合理的編碼用二進位（或任何至少為 2 的底）寫數字，用鄰接表或矩陣列出圖，諸如此類。拯救我們的深層事實是：同一物件的所有合理編碼，其大小彼此之間只差一個多項式關係，所以在某一種合理編碼下是多項式時間的問題，在所有合理編碼下也都是多項式時間。

這就是為什麼複雜度理論能談論一個問題「那個」時間複雜度，而不必執著於格式。只要你避開像一進位灌水或荒謬壓縮這類病態編碼，P 類與多項式時間的界線就不取決於你拼寫輸入的確切方式。固定一個合理的編碼，是讓之後每一句關於效率的論斷都有良好定義的安靜第一步。