如果你在大學裡學過NP難題，你大概會得到這樣的結論：

NP難題在理論上是可解的，但在實務上成本高昂得令人絕望。基本上已經證明不存在好的演算法。

至少這是我當時的理解。幾乎所有我談過的人也是如此。網路上也有很多人這麼說。我一直看到「不行，你做不到。這是NP難題。諸如此類」的討論。這種迷思非常普遍，但這些問題並非無法處理。

當時，我的教授以戲劇性的話語結束了最後一堂課（我稍微意譯了一下）：

現在你們學到，幾乎所有有趣的 are undecidable（不可判定），而剩下的問題中，幾乎所有都是NP難題。這對電腦科學這個學科來說，是棺材上的最後一根釘子。

真是的。我不確定大家是否都得到了如此悲觀的框架，但這或許可以解釋原因。

理論本身沒有錯，但在實務中它常常不相關。當然，你提出的任何演算法在某些輸入上都會爆炸。但你可能在 99.9% 的輸入上獲得快速解決方案。或者在 100% 的相關輸入上。理論並沒有排除這種可能性。

理論上，理論與實務沒有區別。但在實務上，卻有區別。

對於 (1) 和 (2)，最壞情況根本不會發生。我的意思是，安裝套件和型別檢查當然會很慢。但是，至少在我職業生涯中，我從未見過災難性的崩潰。

(3) 和 (4) 在技術上是最佳化問題。大家都知道可以用啟發式方法來解決這些問題，但你不需要犧牲最佳性。我們絕對有工具可以在合理的時間內找到可證明的最佳解決方案。沒有什麼魔法。沒有量子電腦。只是更深入地思考並提出更好的演算法。這就是人們所做的。事實上，在過去幾十年裡，演算法的速度提升已經超越了硬體的增長。總體來看，這篇論文引用了 1991 年到 2015 年間 4500 億倍的速度提升。

最後但同樣重要的是：即使是 (5)，NP難題的原型，也經常被大規模解決。亞馬遜每天都在解決十億個 SMT 問題。SMT 是 SAT 的一個更難的版本。SAT 演算法已經變得如此之好，以至於現在它被認為是簡單的部分。

但如果你遇到了最壞情況呢？你不需要等到宇宙熱寂。一個 HTTP 請求有時也會失敗。設定超時，顯示錯誤訊息，... 你懂的。