請問一下一個演算法？Cook's theorem...

Question

請問有人知道Cook's theorem嗎？
可不可以跟我解釋一下呢？謝謝....
"NP=P if and only if the satisfiability problem is a P problem."

Answer 1

定義：
0. 多項式時間內就可以被算出的的問題，叫 P 問題。（這是我的說明，不是 cook 的定義）
1. 如果一個 decision problem (DP)（答案是 Yes 或 No 的問題）可以用任一種 non-Deterministic 演算法在多項式時間（Polynomial-time，就是它是 O(Nk), k是常數）算出，它就是在 NP (Non-deterministic Polynomial time)的範圍。
2. 一個 DP 叫 NP-complete 如果它是在 NP 範圍內，而且每個在 NP 範圍內的問題都能經由deterministic Turing machine 在多項式時間內推演成它。
3. 一個〝由布林運算去算一些布林變數的布林表示式〞叫一個布林合適實例 (an instance of the Boolean statisfiability problem)。
　如果存在某布林變數初使值，經由這個布林運算，可以算出 True，那這個布林運算就是一個可合適的 (satisfiable)布林運算。（這東東好像叫 SAT）
由上述定義 2. ，NP的問題都能在多項式時間內變成另一個 NP 問題。
如果有一個演算法A，能讓任一NP問題B在多項式時間內被算出（就是變成 P 問題），
那所有的NP都可以在多項式時間內變成B，而由A在多項式時間內被算出。
SAT 是NP問題，所以，SAT 若能在多項式時間內被算出，所有的NP問題一定都(因為 if and only if，所以我加了都字)可以在多項式時間內被算出。
所以，NP問題全都變成P問題了。
註：NP是哪２個字是教授想放水的必考題！
　　你一定要知道，別讓教授連放水都救不了你！
加油！我明年要修 NP Complete and Harder Problems！
圖片參考：http://tw.yimg.com/i/tw/blog/smiley/17a.gif

它只有一個預修課：Algorithm Analysis (AA)！
圖片參考：http://tw.yimg.com/i/tw/blog/smiley/11.gif

AA也只有一個預修課：Algorithm Design！
圖片參考：http://tw.yimg.com/i/tw/blog/smiley/30.gif


2006-12-19 11:21:40 補充：
沒辦法！我的指導教授的博士論文是 NP-Complete problem。
我，我悲慘的命運！