Computer Science > QUESTIONS & ANSWERS > Arizona State UniversityCSE 551CSE551_Week7_Solutionsheet (All)
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
by gjh63826393 · 2 years ago
Connected school, study & course
About the document
Uploaded On
Aug 28, 2021
Number of pages
7
Written in
This document has been written for:
Uploaded
Aug 28, 2021
Downloads
1
Views
124
In Browsegrades, a student can earn by offering help to other student. Students can help other students with materials by upploading their notes and earn money.
We're available through e-mail, Twitter, Facebook, and live chat.
FAQ
Questions? Leave a message!
Copyright © Browsegrades · High quality services·