《算法设计与分析 Design and Analysis of Algorithms》课程PPT课件：Tutorial 10

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