For each of the two questions below, decide whether the answer is (i) “Yes,” (ii
ID: 3776835 • Letter: F
Question
For each of the two questions below, decide whether the answer is
(i) “Yes,” (ii) “No,” or (iii) “Unknown, because it would resolve the question
of whether P = NP.” Give a brief explanation of your answer.
(a) Let’s define the decision version of the Interval Scheduling Problem
from Chapter 4 as follows: Given a collection of intervals on
a time-line, and a bound k, does the collection contain a subset of
nonoverlapping intervals of size at least k?
Question: Is it the case that Interval Scheduling P Vertex Cover?
(b) Question: Is it the case that Independent Set P Interval Scheduling?
Explanation / Answer
a) Yes. Remember that the greedy algorithm utilized to solve the Interval Scheduling problem be O (n log n). The Interval Scheduling problem can be answered in polynomial time without make calls to a black box that solves the Vertex Cover problem. consequently, the interval scheduling problem can be solved by a polynomial number of standard computational steps, advantage a polynomial number of calls to a black box so as to solves Vertex Cover, therefore Interval Scheduling P Vertex Cover.
b) Unknown, as it would resolve the question of whether P=NP.
That is Independent Set P Interval Scheduling P=NP
Proof:
(1) Says: assume Y P X. If X can be solved in polynomial time, next Y can be solved in polynomial time.
Interval scheduling is able to be solved in polynomial time; consequently Independent Set can be solved in polynomial time. Independent Set is NP-complete.
(2) Says: assume X is an NP-complete problem. Next X is solvable in polynomial time if and only if P=NP.
Therefore Independent Set being NP-co mplete and solvable in polynomial time mean P=NP. Independent set is NP. If P=NP, therefore Independent Set is P, i.e. Independent Set is able to be solved in polynomial time. Subsequently Independent Set P Interval Scheduling as Independent Set is able to be solved in polynomial time by a polynomial number of calls to a black box to solve Interval Scheduling, zero calls are needed.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.