NP-complete 筆記

若一個問題能在多項式時間內提求得解答稱為P。
若一個問題非P，但能在多項式時間內驗證一個答案是否正確，稱為NP。
所有NP問題可歸納成不同的NP-Complement問題，
而NP-Complement問題間又已知存在轉換式，若能證明單一NP-Complement為P，
則可證明 P=NP!
常見NP-Complement問題
1.售貨員旅行問題
2.背袋問題
3.包裝問題
或[2][3]

目前可確定 P belong to NP,
但 P=NP? 仍然無法證明之，2002年對100名研究舉行投票，Yes:61, No:9 Unsure:22.

普林斯頓大學資訊工程系建築上的磚牆，用7bits的二進制ASCII碼寫著 P=NP?
使用二進制的理由之一，若證明成立後可簡單改為 P=NP or P=NP!
Image Gallery :: Princeton Computer Science

Reference:
[1] P versus NP problem - Wikipedia, the free encyclopedia
https://secure.wikimedia.org/wikipedia/en/wiki/P_versus_NP_problem
[2] 未來數學家的挑戰 (第 3 頁)
http://episte.math.ntu.edu.tw/articles/mm/mm_10_2_04/page3.html
[3] List of NP-complete problems - Wikipedia, the free encyclopedia
https://secure.wikimedia.org/wikipedia/en/wiki/List_of_NP-complete_problems