NP and Computational Intractability Question #1

Justify your answer

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 Prob- lem 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