[Algorithm] NP

P:
decision problem that can be solved by a deterministic turning machine

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

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

NP-Hard
NP-hard is at least as hard as NP-Complete
至少和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:
證明該問題
(1)屬於NP
(2)屬於NP-Hard

因為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
因為可以互相reduce的關係，我們即證明所有NP-Complete的問題都可以在
polynomial-time 解出來 ，因此證明P=NP

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