Design and Analysis of Algorithms: Tutorial 10 Overview
In this tutorial, Chengyu Lin covers Decision, Search, Optimization, Class P & Class NP Reductions, NP-Completeness, various problem forms, and the three forms of CLIQUE. It delves into Language and Decision Problems, class P versus class NP, deterministic and nondeterministic polynomial time, and their computation models.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCI 3160 Design and Analysis of Algorithms Tutorial 10 Chengyu Lin
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 propertiesif 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 in complexity theory Decision Problem 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 4
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 = ? 00,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 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 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. 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 9
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
Reductions Yes Yes Polynomial Time Reduction Polynomial Time Algorithm for Problem B No No Polynomial Time Algorithm for Problem A If problem A is reducible to problem B in polynomial time, then which problem is easier? A Or B ? Problem B is at least as hard as ProblemA! 11
Two Ways to Use Reductions Suppose Problem A is reducible to Problem B Solve problem If there exists efficient algorithm for Problem B, then we can solve Problem A efficiently Prove Hardness If Problem A is hard, then Problem B is also hard Efficient algorithms Problem A Problem B Reduction Hardness 12
NP-Completeness Problem A is NP-complete if 1. Problem A is in NP 2. For anyProblem A in NP, A is reducible to A in polynomial time Class NPC: The class of all NP-complete problems, which is a subclass of NP The hardest problems in NP Solve a problem in NPC, you can solve ALL problems in NP 13
NP = P ? If NPC P is not empty, then NP = P NP ? P NPC 14
Proof of NP-Completeness Given a Problem A, prove that A is NP-complete Proof Scheme 1 Show Problem A is in NP (easier part) For all Problems in NP, reduce them to A in polynomial time This has been done for 3SAT, the first NP-complete problem Proof Scheme 2 Show Problem A is in NP (easier part) For arbitrary problem A in NPC, reduce A to A in polynomial time This would be much easier 15
NP-completeness of Longest Path Longest Path (Decision Version) Given a graph G and an integer k, decide whether G contains a simple path of length greater than k Part 1 (Longest Path in NP) Given any sequence of vertices, it s easy to check the length and whether the sequence is a path, so Longest Path is in NP Part 2 (reduce special case to general form) The Longest Path contains Hamiltonian Path (k = n) as a special case, so we can reduce Hamiltonian Path (known in NPC) to Longest Path directly 16
Reduce SAT to 3SAT What about reduce general form to special case? This implies that even for the special case, the problem will NOT be easier This may also give clues where the hardness lies in Given an instance (x) of SAT, we transform it to an instance (x,y) of 3SAT ?1 ?2 ?1, ?1 ?3 ?2, ?2 ?4 ?3, ?? 3 ?? 1 ?? ?1 ?2 ?? Clause in (x) Set of clauses in (x,y) 17
Equivalence in Satisfiability () True ?1 ?2 ?1, ?1 ?3 ?2, ?2 ?4 ?3, ?? 3 ?? 1 ?? False False False ?1 ?2 ?? Clause in (x) True True Set of clauses in (x,y) Suppose ?1 ?2 ?? is satisfied by ?, then some ?? must be true Set ?1, ,?? 2 to true, and other?j to false, then the set of clauses are satisfied by ? and ? 18
Equivalence in Satisfiability () ?1 ?2 ?1, ?1 ?3 ?2, ?2 ?4 ?3, ?? 3 ?? 1 ?? ?1 ?2 ?? Clause in (x) Set of clauses in (x,y) Suppose the set of clauses are satisfied by ? and ?, if some ?? is true, then ?1 ?2 ?? is satisfied by ? Otherwise, ?1 should be true, then ?2 is forced to be true and so on. Finally, ?? 3 is also forced to be true, the last clause is not satisfied, contradiction 19
Thank You! Q & A ?
