上一回我們說旅行推銷員問題(TSP)是一個NP困難問題，沒有快速的演算法可以解決。

那一個問題怎樣叫做「困難」，演算法又要多快才叫做快呢？

如果說所有運算問題有容易與困難之分，NP困難的理論用明確的方式作出分野。不深入NP困難的定義、用最最簡單粗淺的方式來說，容易是指可以以多項式時間的演算法解決，困難是指最壞情況需要指數時間。

我們之前討論過的諸多演算法，如二分搜尋、快速排序...執行時間有O(n)，O(log n)、O(n²)、O(n log n)等等。雖然這些執行時間各有不同，n的大小也會依實際問題有所變化，但它們的共通點是都是n的多項式倍數，或者說可以表示為O(n^c)，其中c為一常數。這樣的演算法可以被稱為快速，而能以快速演算法正確解決的問題可以想為是容易的問題。

TSP被認為是困難問題，除了目前沒有快速演算法可以解決，我們甚至還無法證明這樣的快速演算法究竟是 1.存在但尚未找到，還是2.根本不存在，雖然多數科學家更傾向主張第二種情況[註1]。既無從證明快速演算法存不存在，當我們說一個問題困難時，並不是「絕對沒有快速解」的意思，它比較像一種相對的表達，指這個問題至少與其他許多還沒有快速解的困難問題一樣困難。

分辨困難問題

其實現實生活中碰到困難問題的機率並不低，那我們怎麼分辨一個問題是否困難，進而調整策略呢？

一種方法是先熟悉一些已知是困難的問題，碰到新問題時，可以察覺出它們是同一類型問題。例如假設碰到的新問題是要以一個順序解決一系列任務，而且每個任務的成本都跟前一個任務相關，那麼很有可能這其實是個TSP類型的問題，只是問題的描述或對象不同。

另一種方法是運用歸約(reduction)的技巧，進行問題之間的轉換，例如將一個困難的問題化為新問題，可以知道新的問題也是困難的。

應對困難問題

當在現實生活中遇到困難問題，使用已知的快速演算法硬解很有可能是徒勞的，這時候該怎麼辦呢？除非剛好問題規模很小，可以直接解決，不然通常會需在在幾個方面作出取捨。

1. 可能必須為個別問題設計出適用的演算法。例如利用動態規劃解背包問題的例子，即是找到解決特定問題的子問題的方式。
2. 放棄百分之百的正確性，例如使用貪婪演算法，得到可接受的近似解，並節省很多時間。
3. 如果必須追求正確解，只能盡可能地縮短執行時間。也就是雖然沒有快速演算法可用，至少盡量避免暴力解決法這類最慢的方式，像是利用動態規劃解決TSP就是一個例子。

[註1]有興趣想要了解這個難題可以參考P/NP問題。