NP-hard
NP-hard
NP-hard，其中，NP是指非確定性多項式（non-deterministic polynomial，縮寫NP）。所謂的非確定性是指，可用一定數量的運算去解決多項式時間內可解決的問題。
NP問題通俗來說是其解的正確性能夠被“很容易檢查”的問題，這裡“很容易檢查”指的是存在一個多項式檢查演演算法。若NP中所有問題到某一個問題是圖靈可歸約的，則該問題為NP-hard問題。
例如，著名的推銷員旅行問題（Travel Saleman Problem or TSP）：假設一個推銷員需要從香港出發，經過廣州，北京，上海…，等n個城市，最後返回香港。任意兩個城市之間都有飛機直達，但票價不等。假設公司只給報銷C元錢，問是否存在一個行程安排，使得他能遍歷所有城市，而且總的路費小於C？
推銷員旅行問題顯然是NP的。因為如果你任意給出一個行程安排，可以很容易算出旅行總開銷。但是，要想知道一條總路費小於C的行程是否存在，在最壞情況下，必須檢查所有可能的旅行安排！這將是個天文數字。
旅行推銷員問題是數圖論中最著名的問題之一，即“已給一個n個點的完全圖，每條邊都有一個長度，求總長度最短的經過每個頂點正好一次的封閉迴路”。Edmonds，Cook和Karp等人發現，這批難題有一個值得注意的性質，對其中一個問題存在有效演演算法時，每個問題都會有有效演演算法。
迄今為止，這類問題中沒有一個找到有效的演演算法。傾向於接受NP完全問題（NP-Complete或NPC）和NP難題（NP-Hard或NPH）不存在有效演演算法這一猜想，認為這類問題的大型實例不能用精確演演算法求解，必須尋求這類問題的有效的近似演演算法。
此類問題中，最經典的還有子集和問題；Hamilton迴路問題；最大化問題。
常用的定義是所謂的“關係定義式”。即對於一個語言L，L在NP中，那麼存在多項式時間圖靈機M，和多項式p使得
基本信息
- 外文名
- NP-hard
- 釋義
- 所謂的非確定性
- 作用
- 解決問題
- 全稱
- non-deterministic polynomial