NP-Completeness

在SMK的精湛的教學下，這學期我終於能夠初窺迷惑三年的NP-Completeness，　　Orz..

不過我想若沒有學過"正規語言與自動機"，在腦海中應該很難有個正確的image。

反而看起來有點哲學意味?

P: 能用(deterministic)turing machine在polynomial time 解決的所有decision problem.

NP: 能用non-deterministic machine在polynomial time 解決的所有decision problem.

NP-Hard: 若有一個問題，所有的NP問題都polynomially reducible成它，那它就是NP-Hard problem.
(通常被reducible的問題，常常是較難的問題)

NP-Complete: 若有一個問題本身屬於NP, 而且它也是NP-Hard problem，那麼它就是NP-complete.

P=NP的證法：
若能找到一個NP-Complete的問題，它可以用deterministic machine在polynomial time解決，
即可證明P=NP。(因為所有的NP都polynomially reducible成NP-Complete problem)

NP-Complete的證法:
假設我們要證明的Problem為X.
1.證明X屬於NP Problem(1.guess 2.check　不一定會猜中，但一定會有答案)
2.找另一個NP-Complete的問題，並證明它polynomially reducible成X.
(表示X至少比一個NP-Complete問題難)

所有P,NP都是turing machine decidable problem，
NP-Hard problem則可能是decidable 或 non-decidable。
如:
SAT是NP-Complete，且是Turing Machine decidable，
Halting Probelm是NP-Hard Problem，但是Turing Machine undecidable.