.
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
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.
