Computer Science > QUESTIONS & ANSWERS > Georgia Institute Of Technology - CS 8803CS 8803GA HW6 Practice Solutions (All)

Georgia Institute Of Technology - CS 8803CS 8803GA HW6 Practice Solutions

Document Content and Description Below

CS 8803GA Homework 6 Practice Solutions March 15, 2018 Problem 1: DPV 8.1 TSP Optimization vs Search Recall the traveling salesman problem: TSP Input : A matrix of distances; a budget b Outpus : ... A tour which passes through all the cities and has length ≤ b, if such a tour exists The optimization version of this problem directly asks for the shortest tour. TSP-OPT Input : A matrix of distances Outpus : The shortest tour which passes through all the cities. Show that if TSP can be solved in polynomial time, then so can TSP-OPT. Solution. In order to show this, we will show that TSP-OPT reduces to TSP in polynomial time. The idea of this reduction is to use binary search with the b input for TSP to find the length of the shortest tour (then TSP will find the shortest tour itself). Let ts. Prove that Stingy SAT is NP-complete. Solution. First, we show that Stingy SAT is in NP. Let the input formula be denoted by f, and let n be the number of variables and m be the number of clauses. Given a satisfying assignment σ of F , we can just check clause by clause that σ satisfies every one; this takes O(n) time per clause and thus O(nm) total time. Then in O(n) time, we count how many variables are set to be TRUE in σ and check that the number is larger than k or not. Now, we show: SAT ! Stingy SAT. Suppose you have an input formula f for SAT with n variables and m clauses. Now, run Stingy SAT on f with k = n. Clearly, every assignment over n variables will have at most n variables set to true, so this extra restriction will not constrain the set of solutions. Then, if Stingy SAT returns a satisfying assignment, that assignm [Show More]

Last updated: 2 years ago

Preview 1 out of 6 pages

Buy Now

Instant download

We Accept: