Proving NP Complete Problems Show that one of the following problems is polynomi

Question

Proving NP Complete Problems

Show that one of the following problems is polynomially 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

Both the problems a and b are NP problems

But if we can solve the polynomial for problem a then it can also be helpful to solve problem b. So, we can say that statment b is polynomially reducible to statement a.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.