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
Class p v.s. Class NP P stands for what? Polynomial! Class p: Problems solvable in deterministic polynomial time What about np? ☆ No Prob|em? 8 Not Polynomial (i.e. polynomial time unsolvable Nondeterministic Polynomial! Class Np: Problems solvable in nondeterministic polynomial time
Class P V.S. Class NP • P stands for what? Polynomial! • Class P: Problems solvable in deterministic polynomial time • What about NP? ❖ No Problem? ❖ Not Polynomial (i.e. polynomial time unsolvable)? Nondeterministic Polynomial ! • Class NP: Problems solvable in nondeterministic polynomial time 6
Deterministic/Nondeterministic Polynomial time? Where do these terms come from? They're based on different computation models Deterministic Turing Machine 4 Nondeterministic Turing Machine We will not talk about Turing Machine in this course Details of these computation models please refer to the following course A CSCI3130 (Formal Languages and Automata Theory)
Deterministic/Nondeterministic Polynomial time? • Where do these terms come from? • They’re based on different computation models ❖ Deterministic Turing Machine ❖ Nondeterministic Turing Machine • We will NOT talk about Turing Machine in this course • Details of these computation models, please refer to the following course ❖ CSCI3130 (Formal Languages and Automata Theory) 7
An Equivalent Definition of Class NP Class NP: Problems checkable or verifiable in polynomial time Verification: Given a"certificate"of a solution, we could verify that the certificate is correct, e. g 8 Certificate for sat would be an assignment 8 Certificate for hamiltonian Cycle would be a sequence of n vertices, V1, V2, .. ,Vn
An Equivalent Definition of Class NP Class NP: Problems checkable or verifiable in polynomial time Verification: ❖Given a “certificate” of a solution, we could verify that the certificate is correct, e.g. ❖Certificate for SAT would be an assignment ❖Certificate for Hamiltonian Cycle would be a sequence of n vertices, v1 , v2 , …, vn 8
Solvable v.s. Verifiable For a problem in p we have polynomial time algorithm to solve it For a problem in NP, we have polynomial time verification algorithm to verify a certificate
Solvable V.S. Verifiable • For a problem in P, we have polynomial time algorithm to solve it • For a problem in NP, we have polynomial time verification algorithm to verify a certificate 9
Reductions Reduction: a transformation between instance a of Problem a and instance p of problem b such that The transformation takes polynomial time polynomial in size of the input instance The answer for a is yES"if and only if the answer forβ is also"Es
Reductions Reduction: a transformation between instance α of Problem A and instance β of Problem B such that • The transformation takes polynomial time ❖ Polynomial in size of the input instance • The answer for α is “YES” if and only if the answer for β is also “YES” 10