Arizona State UniversityCSE 551CSE551_Week7_Solutionsheet

Document Content and Description Below

CSE 551: Quiz 7 Solutions ASU, Summer 2019 July 3, 2019 1 Problem 1 Which of the following problems does not likely have a polynomial-time algorithm? Select all that apply. • Vertex Cover •... Shortest Path • Knapsack • Minimum Cut 1.1 Rationale VERTEX-COVER and KNAPSACK are both NP-Complete problems. If one were to find a polynomial time algorithm that solves either of these, it would prove P=NP. 12 Problem 2 What is a decision problem? • A problem in which the answer is always yes or no. • A problem that requires any algorithm for it to make a decision. • A problem that is in P or NP. • A problem that requires any algorithm for it to return a result that is not a boolean value. 2.1 Rationale A decision problem is a problem that can be answered either yes or no by a Turing machine given an instance and a parameter. More specifically, the Turing Machine decides whether an input string is an element of the language it recognizes. 3 Problem 3 Why, informally, is P a subset of NP? • Because the certificate could be the algorithm itself, and the certifier could be the execution of the algorithm. • Because an NP algorithm would be to simulate the P algorithm. • Because any polynomial-time algorithm obviously runs in polynomialtime. • Because it follows directly from the definition. 3.1 Rationale For any problem that can be solved in polynomial time we can demonstrate that a certificate is correct simply by running the full algorithm, which will, of course, execute in polynomial time. 24 Problem 4 Which of the following is a valid statement about problem Y for when (X ≤P Y ) and (X) is guaranteed to be polynomial-time solvable? [Show More]

Last updated: 1 year ago

Preview 1 out of 7 pages