2015年6月14日 星期日

Formal Language - Ch16.5 Cook-Levin理論與卡普的二十一個NP-完全問題

 

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理論





技術提供:Blogger.