.
.
P, NP, coNP, NP-COMPLETE, NP-HARD
[ class P ] : 可以用 Polynomial 演算法解決的問題，亦即解決時間為 Polynomial time.
DEFINITION : The class of languages that are Decidable in Polynomial time on a Deterministic single-tape Turing Machine.
=> 在 Deterministic 單 tape TM 上, 所有多項式時間內可解的 Decidable 語言所成的集合.
=> 多項式時間, 亦即 t(n), 也就是 n 的 k 次方
Example：
1. PATH(有向圖的路徑問題) ∈ P
2. RELPRIME(互為質數問題) ∈ P
3. CFL(Every Context-free language) ∈ P
[ class NP ] : 可以用 Non-deterministic Polynomial 演算法解決的問題.
DEFINITION : The class of languages that have Polynomial time Verifiers.
THEOREM : A language is in NP iff it is decided by some Non-deterministic Polynomial time Turing Machine.
=> 在 Nondeterministic TM (NTM N) 上, 多項式時間內可解的 Decidable 語言所成的集合.
=> Nondeterministic 就是 多管齊下 ! 而 Verifying is easy, Determinig is hard.
Example :
1. CLIQUE (k-clique : Graph裡有k個nodes, 是彼此相連的) ∈ NP
亦即 CLIQUE = { G is an undirected graph with k-clique } ∈ NP
(Proof : The clique is the certificate. )
V = "On input < , c > :
1. Test whether c is a set of k nodes in G
2. Test Whether G contains all edges connecting nodes in c
3. If both pass, ACCEPT; Otherwise, REJECT."
(Proof : by NTM. )
N = "On input , where G is a graph :
1. Nondeterministically select a subset c of k nodes of G
2. Test whether G contains all edges connecting nodes in c
3. If yes, ACCEPT; Otherwise, REJECT."
2. SUBSET-SUM Problem (子集之和) ∈ NP
亦即 SUBSET-SUM = { S = {x1, ...,xk} and for some {y1,...,yk} ⊆ {x1,...,xk}, we have ∑ yi = t } ∈ NP
( 比如說：S = < { 2, 3, 8, 31, 40, 44 }, 45 > 中, 因為 3 + 3 + 8 + 31 = 45 ...
所以 S 就是 SUBSET-SUM )
(Proof : The subset is the certificate. )
V = "On input < , c > :
1. Test whether c is a collection of numbers that sum to t
2. Test whether S contains all the numbers in c
3. If both pass, ACCEPT; Otherwise, REJECT."
(Proof : by NTM. )
N = "On input :
1. Nondeterministically select a subset c of the numbers in S
2. Test whether c is a collection of numbers that sum to t
3. If the test pass, ACCEPT; Otherwise, REJECT."
[ class coNP ] : which contains the languages that are complements of languages in NP. (NP的補數)
[ P vs NP ] :
P = the class of languages for which membership can be DECIDED quickly.
NP = the class of languages for which membership can be VERIFIED quickly.
[ P = NP ? ] 或是 [ P ≠ NP ? ] :
This is the greatest unsolved problems in Theoretical Computer Science and Contemporary Mathmatics.
[ NP-COMPLETE ] :
DEFINITION : A language B is NP-complete if it satisfies two conditions :
1. B is in NP, and
2. every A in NP is polynomial time reducible to B. (此2.亦即 NP-Hard)
[ Polynomial time mapping reducible ] :
DEFINITION : Language A is Polynomial Time Mapping Reducible to language B, written A ≤p B ,
if a Polynimial time computable function f : ∑* -> ∑* exists, where for every w,
w ∈ A <=> f(w) ∈ B
The function f is called the Polynomial time reduction of A to B.
=> This is also called [ Polynomial Time Reducible ] or [ Polynomial Time many-one reducibility ]
[ NP-Hard ] :
Every A in NP is polynomial time reducible to B.
=> 任何 Language in NP 問題, 都可 Polynomial time reducible to B
=> 若一 Problem, 是 NP Problem, 又是 NP-Hard Problem, 則就是NP-Complete Problem.
.jpg)
