NP-完備的概念是在1960晚期和1970初期，被美國和蘇聯的研究者於同一時期分別建立起來。
在1971年的美國, 史提芬·古克發表了他的論文"The complexity of theorem proving procedures"於新成立的ACM Symposium on Theory of Computing內。理察·卡普接續的論文"Reducibility among combinatorial problems"則藉由提出了二十一個NP-完全問題的列表，讓古克之前的論文重新受到了注意。古克和卡普因為這個成就得到了圖靈獎。
史提芬·庫克 Stephen A. Cook
史提芬·A·庫克 (Stephen A. Cook，1939年12月14日－)，計算機科學家，計算複雜性理論的重要研究者。
1971年，在他的論文《The Complexity of Theorem Proving Procedures》，他整理了NP完備性的目標，亦產生了庫克定理—布爾可滿足性問題是NP完備的證明。
1982年，庫克得到圖靈獎。因為其論文開啟了NP完備性的研究，令這個領域於之後的十年成為計算機科學中最活躍和重要的研究。
庫克現為多倫多大學的計算機科學和數學系教授。
經歷
庫克1961年從密西根大學獲得了學士學位，並分別於1962年和1966年在哈佛大學獲得碩士和博士學位，1966年，他加入了加州大學伯克萊分校數學系擔任助理教授，直到1970年，他沒有獲得續任。(好慘QQ...)
在慶祝伯克萊EECS系30週年的演講中，圖靈獎獲得者和伯克利的教授理查德·卡普說，「這是我們永遠的恥辱，我們無法說服數學系給他的任期。」
1970年，庫克轉往多倫多大學計算機科學與數學系任教，擔任副教授，1975年晉升為教授，於1985年成為傑出教授。
Cook-Levin理論
在計算複雜度理論內，Cook–Levin理論或者Cook理論，證明了布爾可滿足性問題(SAT)是NP完全問題。換句話說，任何NP裡面的問題可以在多項式時間內，使用圖靈機，將之歸約成「一個布林方程式是否存在解」這個問題。
這理論一個非常重要的結果是，如果存在一個決定型多項式時間演算法，可以解決SAT的話，則對於所有的 NP裡面的問題都存在決定型多項式時間演算法，因此複雜度類NP就會等於複雜度類P。
有關以上這個演算法存在與否的問題，又被稱為P/NP問題。而且廣泛認為這是現在的理論電腦科學裡面，最重要的未解問題。
布爾可滿足性問題
布爾可滿足性問題的成員(instance)是一個布爾表達式，也就是一些布爾變數跟布爾邏輯運算符的組合。
如果說一個表達式是可滿足的(satisfiable)，則存在某些給予布爾變數真值的方式，可以使這個表達式的值為真。
理察·曼寧·卡普 Richard Manning Karp
理察·曼寧·卡普（Richard Manning Karp，1935年1月3日－），是一位計算機科學家以及計算理論家。為柏克萊加州大學教授，在演算法理論方面有卓越的貢獻，因此獲得1985年的圖靈獎，2004年的富蘭克林獎章（Benjamin Franklin Medal），2008年的京都賞（Kyoto Prize）。
卡普的二十一個NP-完全問題
在計算複雜度理論內，一個極度重要的成就是史提芬·古克在 1971證明出了第一個NP-完全 problem問題 — 布爾可滿足性問題。在1972年，理察·卡普將這個想法往前推進，發表了他著名的論文"Reducibility Among Combinatorial Problems"，其內證明了21個不同的，均因為其難解而惡名昭彰的組合數學與圖論問題，是NP-完全問題。
藉由展示出許多研究上面重要的問題是NP-完全問題，卡普促進了研究NP，NP-完備性，以及現在著名的P = NP這些問題。
- 布爾可滿足性問題（Satisfiability）：對於布爾邏輯內合取範式方程式的滿足性問題（一般直接叫做SAT）
- 0-1 整數規劃（0-1 integer programming）
- 分團問題（Clique）（參考獨立集）
- Set packing(Set packing)
- 最小頂點覆蓋問題（Vertex cover）
- 集合覆蓋問題(Set covering)
- Feedback node set（Feedback node set）
- Feedback arc set
- 有向哈密頓迴圈 (卡普命名，現稱Directed Hamiltonian cycle)
- 無向哈密頓迴圈 (卡普命名，現稱Undirected Hamiltonian cycle)
- 每句話至多3個變量的布爾可滿足性問題 (Satisfiability with at most 3 literals per clause, 3-SAT)
- 圖著色問題（Chromatic number）
- 分團覆蓋問題（Clique cover）
- 精確覆蓋問題（Exact cover）
- Hitting set（Hitting set）
- Steiner tree（Steiner tree）
- 三維匹配問題（3-dimensional matching）
- 背包問題（Knapsack）
- Job sequencing（Job sequencing）
- 劃分問題（Partition）
- 最大割（Max cut）
References
Cook-Levin理論
http://zh.wikipedia.org/wiki/Cook-Levin理論
發表文章
沒有留言:
張貼留言