基本簡介
多流水線調度實際上是一個NP完全問題數學上著名的NP問題，完整的叫法是NP完全問題，也即“NP COMPLETE”問題，簡單的寫法，是 NP=P？的問題。問題就在這個問號上，到底是NP等於P，還是NP不等於P。證明其中之一，便可以拿百萬美元大獎。
這個獎還沒有人拿到，也就是說，NP問題到底是Polynomial，還是Non-Polynomial，尚無定論。
NP裡面的N，不是Non-Polynomial的N，是Non-Deterministic，P代表Polynomial倒是對的。NP就是Non-deterministic Polynomial的問題，也即是多項式複雜程度的非確定性問題。
美國麻州的克雷(Clay)數學研究所於2000年5月24日在巴黎法蘭西學院宣布了一件被媒體炒得火熱的大事：對七個“千僖年數學難題”的每一個懸賞一百萬美元。以下是這七個難題。
“千僖難題”之一： P (多項式算法)問題對NP (非多項式算法)問題
“千僖難題”之二： 霍奇(Hodge)猜想
“千僖難題”之三： 龐加萊(Poincare)猜想
“千僖難題”之四： 黎曼(Riemann)假設
“千僖難題”之五： 楊－米爾斯(Yang-Mills)存在性和質量缺口
“千僖難題”之六：納維葉－斯托克斯(Navier-Stokes)方程的存在性與光滑性
“千僖難題”之七：貝赫(Birch)和斯維訥通－戴爾(Swinnerton-Dyer)猜想
NP完全問題排在百萬美元大獎的首位，足見他的顯赫地位和無窮魅力。
問題詳解
遺傳算法是解決NP問題的一種較理想的方法。NP就是Non-deterministic Polynomial的問題，也即是多項式複雜程度的非確定性問題。
什麼是非確定性問題呢？有些計算問題是確定性的，比如加減乘除之類，你只要按照公式推導，按部就班一步步來，就可以得到結果。但是，有些問題是無法按部就班直接地計算出來。比如，找大質數的問題。有沒有一個公式，你一套公式，就可以一步步推算出來，下一個質數應該是多少呢？這樣的公式是沒有的。再比如，大的合數分解質因數的問題，有沒有一個公式，把合數代進去，就直接可以算出，它的因子各自是多少？也沒有這樣的公式。
這種問題的答案，是無法直接計算得到的，只能通過間接的“猜算”來得到結果。這也就是非確定性問題。而這些問題的通常有個算法，它不能直接告訴你答案是什麼，但可以告訴你，某個可能的結果是正確的答案還是錯誤的。這個可以告訴你“猜算”的答案正確與否的算法，假如可以在多項式時間內算出來，就叫做多項式非確定性問題。而如果這個問題的所有可能答案，都是可以在多項式時間內進行正確與否的驗算的話，就叫完全多項式非確定問題。
完全多項式非確定性問題可以用窮舉法得到答案，一個個檢驗下去，最終便能得到結果。但是這樣算法的複雜程度，是指數關係，因此計算的時間隨問題的複雜程度成指數的增長，很快便變得不可計算了。
人們發現，所有的完全多項式非確定性問題，都可以轉換為一類叫做滿足性問題的邏輯運算問題。既然這類問題的所有可能答案，都可以在多項式時間內計算，人們於是就猜想，是否這類問題，存在一個確定性算法，可以在指數
時間內，直接算出或是搜尋出正確的答案呢？這就是著名的NP=P？的猜想。
解決這個猜想，無非兩種可能，一種是找到一個這樣的算法，只要針對某個特定NP完全問題找到一個算法，所有這類問題都可以迎刃而解了，因為他們可以轉化為同一個問題。另外的一種可能，就是這樣的算法是不存在的。那么就要從數學理論上證明它為什麼不存在。
前段時間轟動世界的一個數學成果，是幾個印度人提出了一個新算法，可以在多項式時間內，證明某個數是或者不是質數，而在這之前，人們認為質數的證明，是個非多項式問題。可見，有些看來好象是非多項式的問題，其實是多項式問題，只是人們一時還不知道它的多項式解而已。
上回說到可憐的旅行商想找出走遍所有城市的最短路徑。讓我們用計算機幫他搜尋一下。
這就需要用到本篇文章中要介紹的第一門學科了：《人工智慧》。人類的許多活動，如解算題、猜謎語、進行討論、編制計畫和編寫電腦程式，甚至駕駛汽車和騎腳踏車等等，都需要"智慧型"。如果機器能夠執行這種任務，就可以認為機器已具有某種性質的"人工智慧"。現在我們就要利用人工智慧，用計算機模擬人的思維來搜尋最短路徑。
想像一下，我們人思考問題時，有兩種方法：一種是精確搜尋，就是試驗所有的可能性，找出最精確的一個方案。但它在搜尋過程中不改變搜尋策略，不利用搜尋獲得的中間信息，它盲目性大，效率差，用於小型問題還可以，用於大型問題根本不可能；另一種叫做啟發式搜尋，它在搜尋過程中加入了與問題有關的啟發性信息，用以指導搜尋向著一個比較小的範圍內進行，加速獲得結果。
搜尋方法
1.近鄰法(nearest neighbor)
推銷員從某個城鎮出發，永遠選擇前往最近且尚未去過的城鎮，最後再返回原先的出發點。這方法簡單，也許是多數人的直覺做法，但是近鄰法的短視使其表現非常不好，通常後段的路程會非常痛苦。
2.插入法(insertion)
先產生連線部分點的子路線，再根據某種法則將其它的點逐一加入路線。比如最近插入法(nearest insertion)，先針對外圍的點建構子路線，然後從剩餘的點裡面評估何者加入後路線總長度增加的幅度最小，再將這個點加入路線。又比如最遠插入法(farthest，insertion)，是從剩餘的點裡面選擇距離子路線最遠的點，有點先苦後甜的滋味。
3.模擬退火算法(Recuit Algorithm)
模擬退火算法來源於固體退火原理，將固體加溫至充分高，再讓其徐徐冷卻，加溫時，固體內部粒子隨溫升變為無序狀，內能增大，而徐徐冷卻時粒子漸趨有序，在每個溫度都達到平衡態，最後在常溫時達到基態，內能減為最小。根據Metropolis準則，粒子在溫度T時趨於平衡的機率為e-ΔE/(kT)，其中E為溫度T時的內能，ΔE為其改變數，k為Boltzmann常數。用固體退火模擬組合最佳化問題，將內能E模擬為目標函式值f，溫度T演化成控制參數t，即得到解組合最佳化問題的模擬退火算法：由初始解i和控制參數初值t開始，對當前解重複“產生新解→計算目標函式差→接受或捨棄”的疊代，並逐步衰減t值，算法終止時的當前解即為所得近似最優解。
4.遺傳算法
遺傳算法是仿真生物遺傳學和自然選擇機理，通過人工方式所構造的一類搜尋算法，從某種程度上說遺傳算法是對生物進化過程進行的數學方式仿真。生物種群的生存過程普遍遵循達爾文進化準則，群體中的個體根據對環境的適應能力而被大自然所選擇或淘汰。進化過程的結果反映在個體的結構上，其染色體包含若干基因，相應的表現型和基因型的聯繫體現了個體的外部特性與內部機理間邏輯關係。通過個體之間的交叉、變異來適應大自然環境。生物染色體用數學方式或計算機方式來體現就是一串數碼，仍叫染色體，有時也叫個體；適應能力是對應著一個染色體的一個數值來衡量；染色體的選擇或淘汰則按所面對的問題是求最大還是最小來進行。
5.神經網路算法
根據一個簡化的統計，人腦由百億條神經組成 — 每條神經平均連結到其它幾千條神經。通過這種連結方式，神經可以收發不同數量的能量。神經的一個非常重要的功能是它們對能量的接受並不是立即作出回響，而是將它們累加起來，當這個累加的總和達到某個臨界閾值時，它們將它們自己的那部分能量傳送給其它的神經。大腦通過調節這些連結的數目和強度進行學習。儘管這是個生物行為的簡化描述。但同樣可以充分有力地被看作是神經網路的模型。
難度結果
雖然百萬美元的獎金和大量投入巨大卻沒有實質性結果的研究足以顯示該問題是困難的，還有一些形式化的結果證明為什麼該問題可能很難解決。
最常被引用的結果之一設計神喻。假想你有一個魔法機器可以解決單個問題，例如決定一個給定的數字是否為質數，但可以瞬間解決這個問題。我們的新問題是，若我們被允許任意利用這個機器，是否存在我們可以在多項式時間內驗證但無法在多項式時間內解決的問題？結果是，依賴於機器能解決的問題，P = NP和P ≠ NP二者都可以證明。這個結論的後果是，任何可以修改來證明該機器的存在性的結果不能解決問題。不幸的是，幾乎所有經典的方法和大部分已知的方法可以這樣修改（我們稱它們在相對化）。
如果這還不算太糟的話，1993年Razborov和Rudich證明的一個結果表明，給定一個特定的可信的假設，在某種意義下“自然”的證明不能解決P = NP問題。這表明一些現在似乎最有希望的方法不太可能成功。隨著更多這類的定理得到證明，該定理的可能證明有越來越多的陷阱要規避。這實際上也是為什麼NP完全問題有用的原因：若有一個多項式時間算法，或者沒有一個這樣的算法，對於NP完全問題存在，這將用一種相信不被上述結果排除在外的方法來解決P = NP問題。P=NP問題可以用邏輯命題的特定類的可表達性的術語來重新表述。所有P中的語言可以用一階邏輯加上最小不動點操作（實際上，這允許了遞歸函式的定義）來表達。類似地，NP是可以用存在性二階邏輯來表達—也就是，在關係、函式、和子集上排除了全域量詞的二階邏輯。多項式等級，PH中的語言對應與所有的二階邏輯。這樣，“P是NP的真子集嗎”這樣的問題可以表述為“是否存在性二階邏輯能夠表達帶最小不動點操作的一階邏輯的所不能表達的語言？”
普林斯頓大學計算機系樓將二進制代碼表述的“P=NP?”問題刻進頂樓西面的磚頭上。如果證明了P=NP，磚頭可以很方便的換成表示“P=NP！”。康奈爾大學的Hubert Chen博士提供了這個玩笑式的P不等於NP的證明：“反證法。設P = NP。令y為一個P = NP的證明。證明y可以用一個合格的計算機科學家在多項式時間內驗證，我們認定這樣的科學家的存在性為真。但是，因為P = NP，該證明y可以在多項式時間內由這樣的科學家發現。但是這樣的發現還沒有發生（雖然這樣的科學家試圖發現這樣的一個證明），我們得到矛盾。
