NP Problem

這一、兩天花了一些時間在研究啥是NP,NP-Complete,NP hard,

首先介紹P,是找得到polynomial time可解決的problem,

而NP problem 就是Non-determistic polynomial time problem,

也就是找得到nd-choice在polynomial time可解決的problem.

至於NP hard:有一problem X,而所有的NP problem在polynomial time可reduce to X,

稱problem X為NP hard.

在這邊reduce指的是: A is reducible to problem B, 表示解了B就可以解決A問題,所以計算A問題,

不比計算B問題複雜(A cannot be harder than solving B)

NP-Complete:若是一個problem 屬於NP,也屬於NP hard,則此problem 是NP-COmplete.

而且若是一個NP-Complete problem存在一polynomial time的解法，

則所有NP problem都有 polynomial time的解法。