把 P 等同於可行的侷限(limits of identifying P with feasible)
把 P 這個類別等同於「可行」,是複雜度理論擁有的最好的簡單規則,而它對的時候遠多於錯的時候。但值得使用的規則也值得質疑,謹慎的學習者應把這個等式當作有用的理想化,而非字面上的真理。該記住的圖像是一張以大陸尺度繪製的地圖:用來看出多項式與指數是不同的國度極佳,但太粗糙,無法告訴你某個特定小鎮是否有條好路。
這個等式在兩個相反的方向上失靈。一個方向:屬於 P 不保證有可用的演算法。執行時間為 n^100、或為 c 乘以 n(常數 c 等於 10^40),按定義是多項式,卻可能在宇宙壽命內對任何輸入都跑不完;理論家稱這些為「銀河演算法」,徒有多項式之名。另一個方向:在 P 之外(或最壞情況難解)不保證無用。最壞情況分析可能極度悲觀:線性規劃的單純形法在最壞情況下是指數級的,實務上卻極為出色;而許多 NP 困難問題在真實實例上靠啟發式、近似、或因典型輸入遠比最壞容易,而被例行解決。平均情況行為可能與最壞情況完全分道揚鑣。
這一切都不會把 P 拉下王座;它只是誠實地為 P 定位。P 仍是「高效」的標準、與模型無關、對組合友善的定義,是正確的預設與正確的教學說法,正因為其他替代方案更雜亂、更不穩健。所需的紀律只是記住「P 等於可行」是哪一種陳述:一個尖銳、可證明、漸近的理想化,掌握了多項式對指數的峽谷,而非關於前頭那個常數、指數的大小、或某演算法在你實際遇到的輸入上如何表現的承諾。如此理解,P 是你揮舞的工具,而非你崇拜的偶像。
一個跑在 n^100 時間的演算法屬於 P,但對 n = 10 它要花 10^100 步,多於宇宙中的原子數:是多項式,卻是個銀河演算法。反過來,單純形法在最壞情況下是指數級的,卻能在片刻間解出有數百萬變數的真實線性規劃。P 兩種微妙之處都掌握不到;它只掌握多項式對指數的分界。
P 掌握的是多項式對指數的分界,而非常數、指數的大小、或典型情況的行為。
P 是「可行」的標準理想化,而非字面同義詞:一個 n^100 或巨大常數的演算法雖屬於 P 卻毫無用處,而一個最壞情況困難的問題在實際出現的輸入上可能很容易。把 P 當工具,別當偶像。