CSCI 3160 Design and Analysis of Algorithms Tutorial 10 Chengyu Lin
CSCI 3160 Design and Analysis of Algorithms Tutorial 10 Chengyu Lin
Ou uTIne Decision, Search and Optimization Class p& class np Reductions NP-Completeness
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
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 G, find a largest clique in G
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 anguage A language L is just a subset of [0, 1 *, the set of all strings of bits ☆{0,13=Un≥00,1 Language to Decision Problem Given a bit string x, decide whetherxE L 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
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