Design & Theory of Algorithms
Design & Theory of Algorithms CSE 830
Popular in Course
Popular in Computer Science and Engineering
This 5 page Class Notes was uploaded by Donnell Kertzmann on Saturday September 19, 2015. The Class Notes belongs to CSE 830 at Michigan State University taught by Eric Torng in Fall. Since its upload, it has received 44 views. For similar materials see /class/207412/cse-830-michigan-state-university in Computer Science and Engineering at Michigan State University.
Reviews for Design & Theory of Algorithms
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/19/15
Hardness Results for Problems 0 Outline of main concepts to cover 7 The class of easy to solve problems P 7 Absolute hardness results gtk Adversary arguments as a technique for proving absolute hardness results 7 Relative hardness results gtk Reductions as a technique for proving relative hardness results i The class of easy to verify problems NP 7 The concepts of NP completeness and NP hardness Cook7s Theorem proving a rst NP complete problem 0 Fundamental setting 7 When faced with a new problem l l7 we go back and forth between the following two goals 1 Find a good that is polynomial time algorithm for solving H gtk Use the greedy7 dynamic programming7 divide and conquer7 etc algorithm design techniques 2 Prove a hardness result for problem H gtk Adversary argument gtk Information theory argument gtk Reduction argument 0 Complexity class P i P is the set of problems that can be solved using a polynomial time algorithm gtk Sometimes we restrict P to the set of decision problems that can be solved using a polynomial time algorithm gtk A decision problem is a problem where the task is to answer a yesno question i If a problem is in P7 it is generally considered to be ef ciently solvable If a problem is not in P7 it is generally considered to NOT be ef ciently solvable Looking back at the two tasks7 the goal of the rst task is to prove that H is in P and the goal of the second task is to prove that H is NOT in P Absolute Hardness Results 0 Fuzzy De nition 7 A hardness result for a problem without reference to another problem gtk This classi cation need not be precise 0 Examples 7 Solving the independent set problem requires time in the worst case Solving the independent set problem requires 92 time in the worst case 0 Techniques Diagonalization we don7t cover in this course i Information Theory Argument see book Adversary Argument gtk Prove that solving the graph connectivity problem requires 90 time where n is the number of nodes gtk Prove that solving the independent set problem requires 90 time where n is the number of nodes 0 How successful have we been at proving absolute hardness results that show that natural problems are not in P 7 Few natural problems have been proven to not be in P gtk Variants of the Halting problem 7 Many natural problems cannot be placed in or out of P gtk SATlSFlABlLlTY gtk HAMILTONlAN PATH gtk INDEPENDENT SET Relative Hardness Results 0 Fuzzy de nition Hardness result for a problem relative to another problem 0 Examples SATlSFlABlLlTY is at least as hard as HAMlLTONlAN PATH to solve lf SATlSFlABlLlTY is unsolvable then HAMlLTONlAN PATH is unsolvable 7 If SATlSFlABlLlTY is in P then HAMILTONlAN PATH is in P 0 Motivation 7 We are primarily interested in relative hardness results because of our inability to prove absolute hardness results Stated another way if we could prove strong absolute hardness results we would not be as interested in relative hardness results 0 How do we obtain a relative hardness result that problem H1 is at least as hard a problem H2 lnformal We show how to solve problem H1 using a procedure P2 that solves problem H2 as a subroutine gtk There are constraints on how we can use P2 but we ignore these formal details for now 0 Example relative hardness result proofs Multiplication and squaring gtk Squardx multxz proves multiplication is at least as hard as squaring gtk Multxy squardz y 7 squarew 7 proves squaring is at least as hard as multiplication Assumes that addition subtraction and division by 4 can be done with no substantial increase in complexity Speci c complexity of multiplication may be higher as there are two calls to square but the difference is polynomially bounded Reductions 0 We now restrict our attention to decision problems 7 Almost all natural problems can be converted into a decision problem without changing the complexity of the problem 7 Example Decision TSP problem gtk lnput List of cities intercity distances integer bound B gtk YesNo Question Does there exist a tour of the cities with total length at most B Adding this extra input variable that represents the answer often works Show that if we can solve the Decision TSP problem in polynomial time then we can solve the original TSP problem in polynomial time 7 Decision problems are convenient because we can classify inputs into two categories gtk Yes input instances where the correct answer is yes gtk No input instances where the correct answer is no 0 This leads us to the reduction technique for proving relative hardness results where we transform inputs from H1 into inputs of H2 preserving77 yes and no inputs in the transformation process 0 Many one Reductions De nition gtk lnput Decision problem H1 Decision problem H2 gtk Many one reduction R is a function that maps all inputs to H1 to inputs not necessarily all to Hg with the following properties R is computable by an algorithm z is a yes input to H1 lt gt R is a yes input to H2 gtk We say that H1 Sm H2 7 Relative hardness properties of many one reductions gtk Suppose H1 Sm H2 Theorem lf H1 gm H2 and H2 is solvable then H1 is solvable Theorem lf H1 gm H2 and H1 is not solvable then H2 is not solvable Thus in some sense H1 is no harder than H2 However for all solvable problems H1 and H2 H1 ltm H2 and H2 ltm H1 so this is too weak a notion of harder for our purposes 0 Polynomial time Many One Reductions De nition gtk lnput Decision problem H1 Decision problem H2 gtk A polynomial time many one reduction R is a function which maps all inputs to H1 to inputs not necessarily all to Hg with the following properties R is computable by an algorithm which operates within polynomial time z is a yes input to H1 lt gt R is a yes input to H2 gtk We say that H1 17 H2 7 Relative hardness results of polynomial time reductions gtk Suppose H1 17 H2 Theorem lf H1 17 H2 and H2 6 P then H1 6 P Theorem lf H1 17 H2 and H1 Z P then H2 Z P Thus in emactly the sense we want H1 is no harder than H2 0 Example HAMILTONIAN PATH 1 HAMILTONIAN CYCLE 7 HAMILTIONIAN PATH gtk lnput Graph G V E gtk YesNo Question Does there exist a Hamiltonian path a path that visits each node exactly once in G 7 HAMILTIONIAN CYCLE gtk lnput Graph G V E gtk YesNo Question Does there exist a Hamiltonian Cycle a cycle that visits each node exactly once in G 7 Input to reduction input to HAM PATH gtk Graph G V E 7 Output of reduction input to HAM CYCLE gtk Graph G VCE gtk Describe a G7 that satis es the desired property that G is a yes input instance to HAM CYCLE if and only if G is a yes input instance to HAM PATH This proves that HAM PATH is no harder than HAM CYCLE with respect to being in P 0 Example HAMlLTONlAN PATH Sp SATISFIABILITY 7 HAMlLTlONlAN PATH gtk Input Graph G V7 E gtk YesNo Question Does there exist a Hamiltonian Path a path that visits each node exactly once in G 7 SATISFIABILITY gtk lnput Set of variables X Set of clauses G 07 where each clause is a conjunction of literals gtk YesNo Question ls there a truth assignment to the variables that satis es all the clauses Input to the reduction input to HAM PATH gtk Graph G V7 E 7 Output of the reduction input to SAT gtk Boolean expression b in CNF with variables X and clauses G 7 Description of b in terms of G gtk lf lVl 12n7 then X mvl1gz S n Meaning of xiv node 1 is the 2 node of the Hamiltonian path gtk The set of clauses G will enforce this meaning For nodes 1 S 1 S n7 node 1 must appear in the path xlv V 21 V V xm n clauses of length n For nodes 1 S 1 S n7 node 1 must appear only once in the path zm V xjv for 1 S 239 ltj S n 0713 clauses of length 2 For 1 S 239 S 717 some node 1 must be the 2 node in V M2 V 39 39 39 V n clauses of length n
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'