[EE_CSIE] P, NP, coNP, NP-COMPLETE, NP-HARD

. . 

  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.