看板 ott
作者 ott (寶貝)
標題 [Algorithms] P, NP, NP Complete, NP Hard
時間 2013年06月02日 Sun. AM 07:25:05


       
     
   
 

http://www.victorgau.com/?p=477


[Algorithms] P, NP, NP Complete, NP Hard


Posted on November 21, 2011 by Victor


不是 Computer Science 本科生,還真是沒有辦法把 Complexity 懂得透徹。
一般我們用 P, NP, NP Complete 跟 NP Hard 來評估一個問題的複雜度,他到底是甚麼意思呢?

P: 指的是有 Polynomial Time 的解的問題。

NP: 指的是還沒有找到 Polynomial Time 的解,也不確定有沒有 Polynomial Time 的解,但是你一旦提供一個解,這個解可以在 Polynomial Time 被驗證的問題。

NP Complete: 指的也是還沒有找到 Polynomial Time 的解,但是可以在 Polynomial Time 被驗證的問題。但是NPC的問題是NP裡面比較難的問題,所以如果能夠證明NPC的問題有P的解,那NP的問題就都可以找到P的解。

NP Hard: 指的也是還沒有找到 Polynomial Time 的解,但是不確定是不是能在 Polynomial Time 被驗證的問題。NP Hard的問題又比NPC難。

一般來說 P 的問題算是比較簡單,NP Complete 跟 NP Hard 算是很難的問題。而 NP 的問題還是有可能找到快速算法。















 
 









[圖]
 




[圖]
 




[圖]
 








[圖]
 



[圖]
 




[圖]
 



[圖]
 



[圖]
 


 





    
     
   
 


上傳日期:2011-11-23
Beyond Computation: The P vs NP Problem
Michael Sipser, MIT
Tuesday, October 3, 2006 at 7:00 PM
Harvard University Science Center — Hall B
One Oxford Street, Cambridge, MA, 02138

In a remarkable 1956 letter, the great logician Kurt Gödel asked the famous mathematician and computer pioneer John von Neumann whether certain computational problems could be solved without resorting to brute force search.

http://www.claymath.org/public_lectur...

http://www.claymath.org/public_lectur...
類別
教育
授權
標準 YouTube 授權














The Gödel Letter1
Princeton, 20 March 1956

Dear Mr. von Neumann:

With the greatest sorrow I have learned of your illness. The news came to me as quite unexpected. Morgenstern already last summer told me of a bout of weakness you once had, but at that time he thought that this was not of any greater significance. As I hear, in the last months you have undergone a radical treatment and I am happy that this treatment was successful as desired, and that you are now doing better. I hope and wish for you that your condition will soon improve even more and that the newest medical discoveries, if possible, will lead to a complete recovery.

Since you now, as I hear, are feeling stronger, I would like to allow myself to write you about a mathematical problem, of which your opinion would very much interest me: One can obviously easily construct a Turing machine, which for every formula F in first order predicate logic and every natural number n, allows one to decide if there is a proof of F of length n (length = number of symbols).

Let ψ(F,n) be the number of steps the machine requires for this and let φ(n) = maxF ψ(F,n). The question is how fast φ(n) grows for an optimal machine. One can show that φ(n) ≥ k ⋅ n. If there really were a machine with φ(n) ∼ k ⋅ n (or even ∼ k ⋅ n2), this would have consequences of the greatest importance. Namely, it would obviously mean that in spite of the undecidability of the Entscheidungs problem, the mental work of a mathematician concerning Yes-or-No questions could be completely replaced by a machine. After all, one would simply have to choose the natural number n so large that when the machine does not deliver a result, it makes no sense to think more about the problem. Now it seems to me, however, to be completely within the realm of possibility that φ(n) grows that slowly. Since it seems that φ(n) ≥ k ⋅ n is the only estimation which one can obtain by a generalization of the proof of the undecidability of the Entscheidungs problem and after all φ(n) ∼ k ⋅ n (or ∼ k ⋅ n2) only means that the number of steps as opposed to trial and error can be reduced from N to log N (or (log N)2).

However, such strong reductions appear in other finite problems, for example in the computation of the quadratic residue symbol using repeated application of the law of reciprocity. It would be interesting to know, for instance, the situation concerning the determination of primality of a number and how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search.

I do not know if you have heard that “Post’s problem”, whether there are degrees of unsolvability among problems of the form (∃ y) φ(y,x), where φ is recursive, has been solved in the positive sense by a very young man by the name of Richard Friedberg. The solution is very elegant. Unfortunately, Friedberg does not intend to study mathematics, but rather medicine (apparently under the influence of his father). By the way, what do you think of the attempts to build the foundations of analysis on ramified type theory, which have recently gained momentum? You are probably aware that Paul Lorenzen has pushed ahead with this approach to the theory of Lebesgue measure. However, I believe that in important parts of analysis non-eliminable impredicative proof methods do appear.

I would be very happy to hear something from you personally. Please let me know if there is something that I can do for you. With my best greetings and wishes, as well to your wife,

Your very devoted,

Kurt Gödel


P.S. I congratulate you heartily on the … 2






1. The letter was indeed originally written in German. Mike Sipser’s translation can be found in “The History and the Status of the P versus NP Question”, in the 24th STOC proceedings, 1992, pp. 603-618. This also contains a number of other historical quotes. Peter Clote also made a translation to English, which can be found in the book “Arithmetic, Proof Theory and Computational Complexity”, P. Clote and J. Krajicek, eds., Oxford Univ. Press, 1993.
2. The balance of the postscript is missing.











 
 



[圖]

Gödel’s famous 1956 letter to John von Neumann





※ 編輯: ott 時間: 2017-12-27 03:03:14
※ 看板: ott 文章推薦值: 0 目前人氣: 0 累積人氣: 529 
分享網址: 複製 已複製
guest
x)推文 r)回覆 e)編輯 d)刪除 M)收藏 ^x)轉錄 同主題: =)首篇 [)上篇 ])下篇