How to Prove a Problem Is NP-Complete?
在正規語言最後一章中，講到了NP與P problem的差別。
不過在討論NP與P之前，我們必須先知道何謂decision problem。
Decision problem是指給一個問題，此問題的answer is either yes or not。
也就是是非題的概念。
Example：
Peter gives us a map G = (V,E), and he asks us if there is a path from A to B whose length is at most 100
Your sister gives you a number, say 1111111111111111111 (19 one’s), and asks you if this number is a prime
以上兩者皆是decision problem。
P problem：
A decision problem can be solved in polynomial time in the size of input.
NP problem：
A decision problem can be solved by a non deterministic Turing machine in polynomial time in the size of input.(With the power of non deterministic Turing machine, we can guess an answer to the problem.)
Can be verified in polynomial time in the size of input.
By our observation, we have P ⊆ NP.
There will be a question: Is P = NP?
WE DO NOT KNOW THE ANSWER
By Cook-Levin theorem :
If SAT is in P, then all problems in NP are also in P.
Intuitively, SAT must be one of the most difficult problems in NP .
We call SAT an NP-complete problem (most difficult in NP)
SAT is a decision problem the given a Boolean formula F, such as F =
If the answer is YES, F is a satisfiable.
A problem is NP-complete if:
It is in NP.
Every NP problem is reduced to it(in polynomial time).
不過在討論NP與P之前，我們必須先知道何謂decision problem。
Decision problem是指給一個問題，此問題的answer is either yes or not。
也就是是非題的概念。
Example：
Peter gives us a map G = (V,E), and he asks us if there is a path from A to B whose length is at most 100
Your sister gives you a number, say 1111111111111111111 (19 one’s), and asks you if this number is a prime
以上兩者皆是decision problem。
P problem：
A decision problem can be solved in polynomial time in the size of input.
NP problem：
A decision problem can be solved by a non deterministic Turing machine in polynomial time in the size of input.(With the power of non deterministic Turing machine, we can guess an answer to the problem.)
Can be verified in polynomial time in the size of input.
By our observation, we have P ⊆ NP.
There will be a question: Is P = NP?
WE DO NOT KNOW THE ANSWER
By Cook-Levin theorem :
If SAT is in P, then all problems in NP are also in P.
Intuitively, SAT must be one of the most difficult problems in NP .
We call SAT an NP-complete problem (most difficult in NP)
SAT is a decision problem the given a Boolean formula F, such as F =
If the answer is YES, F is a satisfiable.
A problem is NP-complete if:
It is in NP.
Every NP problem is reduced to it(in polynomial time).
留言
張貼留言