HTML Encoder

HTML Encoder

2012年12月2日 星期日

[Algorithm] NP

decision problem that can be solved by a deterministic turning machine

decision problem that can be solved by a non-deterministic turning machine

it is still unknown that P=NP or P != NP

NP-hard is at least as hard as NP-Complete
NP-hard不一定要是decision problem

prove a problem is in NP
1. you can guess a solution in polynomial time
2. you can check the solution in polynomial time

prove a problem is NP-hard
for all NP-Complete problem, if those problems can reduce to this problem, then this problem is NP-Hard
(in practice, 只要找到一個NP-Complete reduce就好)

prove a problem belongs to NP-Complete:

因為NP-Complete有包含NP-Hard 代表他們彼此都可互相reduce
所以其實只要找到一個NP-Complete problem reduce就可以證明該問題屬於NP-Hard

NP-Complete is unlikely to have a polynomial-time solution (still unknown)
只要找到任一個NP-Complete problem的polynomial time solution
polynomial-time 解出來 ,因此證明P=NP

the first NP-Complete problem: SAT
(SATISFIABILITY: the boolean satisfiability problem for formulas in conjunctive normal form)