NP-Completeness: Polynomially Reducible Show that one of the following problems
ID: 3770817 • Letter: N
Question
NP-Completeness: Polynomially Reducible
Show that one of the following problems is polynomials reducible to the other problem: You are melon-selling farmer and you have melons of different weights. A customer comes to you and asks you for exactly k pounds of uncut melons and you need to determine whether you can fulfill his request. A city road network can be described as a set of straight road segments that are connected to a set of intersections. Each police officer, if standing on an intersection can effectively monitor all the segments that are connected to that intersection. The Chief wants to determine whether he can use a force consisting of k police officers so that every segment of the city road network is monitored by at least one police officer.Explanation / Answer
Given an instance of Problem B IB, if there is a polynomial-time Algorithm 1 that we can use to convert the problem to an instance of Problem A IA, such that a ”Yes” answer for IA means a ”Yes” answer for IB and a ”No” answer for IA means a ”No” answer for IB through a polynomial-time transforming Algorithm 2, we say that Problem B can be reduced to Problem A and that Problem A is at least as hard as Problem B
IB -> Algo1 -> IA -> Algo_forA -> No for IA -> No for IB
IB -> Algo1 -> IA -> Algo_forA -> Yes for IA -> Algo2 -> Yes for IB
Here, in our example problem 2 of city network problem is polynomially reducible to problem 1, because we can use some algorithm to convert the the problem 2 of assigning k police officers to every segment to an instance of problem 1 as exactly k uncut melons to be given to customer.
If algorithm gives yes for IA then we can apply it to problem 2 also to get IB as yes...
Hence, problem 2 is pollynomially reducible to problem 1..
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.