amzshar

.

.

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.