For each of the two questions below decide whether the answe

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?

Solution

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.