CSCI 3160 Design and Analysis of Algorithms Tutorial 10 Chengyu Lin
CSCI 3160 Design and Analysis of Algorithms Tutorial 10 Chengyu Lin
Outline Decision,Search and Optimization ·Class P&Class NP 。Reductions ·NP-Completeness 2
Outline • Decision, Search and Optimization • Class P & Class NP • Reductions • NP-Completeness 2
Problems in Different Forms Decision Problem,the answer is simply "YES"or "NO" Search Problem,find a solution satisfying some properties if one exists,else return it doesn't exist Optimization Problem,each solution has an associated value,find a solution with best value (min max) 3
Problems in Different Forms Decision Problem, the answer is simply “YES” or “NO” Search Problem, find a solution satisfying some properties if one exists, else return it doesn’t exist Optimization Problem, each solution has an associated value, find a solution with best value (min / max) 3
Three Forms of CLIQUE Usually,it's enough to consider Decision Problem Decision Problem in complexity theory Given a graph G and a number k,decide whether G has a clique of size≥k ↓no harder than Search Problem Given a graph G and a number k,find a clique with size k in G if one exists,else return it doesn't exist ↓no harder than Optimization Problem Given a graph 6,find a largest clique in G 4
Three Forms of CLIQUE Decision Problem Given a graph G and a number k, decide whether G has a clique of size ≥ k Search Problem Given a graph G and a number k, find a clique with size ≥ k in G if one exists, else return it doesn’t exist Optimization Problem Given a graph G, find a largest clique in G no harder than no harder than Usually, it’s enough to consider Decision Problem in complexity theory 4
Language and Decision Problem are Equivalent Language A language L is just a subset of (0,1)*,the set of all strings of bits {0,1}*=Un≥0{0,1m Language to Decision Problem Given a bit string x,decide whether x EL Decision Problem to Language Given a Decision Problem Encode all the instances into bit strings The corresponding language contains all the strings of "YES"instances 5
Language and Decision Problem are Equivalent Language A language 𝐿 is just a subset of 0,1 ∗ , the set of all strings of bits ❖ 0,1 ∗ = ڂ≤��0 0,1 𝑛 Language to Decision Problem • Given a bit string 𝑥, decide whether 𝑥 ∈ 𝐿 Decision Problem to Language • Given a Decision Problem • Encode all the instances into bit strings • The corresponding language contains all the strings of “YES” instances 5