Justify your answer For each of the two questions below, decide whether the answ
ID: 3716894 • Letter: J
Question
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 SchedulingExplanation / Answer
Is it the case that Interval Scheduling ?P Vertex Cover?
Answer : Usually we use greedy algorithm to solve the Interval Scheduling problem of O(n log n).
The Interval Scheduling problem can be solved in polynomial time without making calls to a black box which solves the Vertex Cover problem.
By using the polynomial number of standard computational steps we can solve the interval scheduling problem.
And a polynomial number of zero calls to a black box which solves the vertex cover,
Hence in this case we proved that Interval Scheduling ?P Vertex Cover.
Is it the case that Independent Set ?P Interval Scheduling?
Answer : Its Unknown, because it would resolve the question of whether P=NP
ie. Independent Set ?P Interval Scheduling ?? P=NP
=> Where Independent Set ?P Interval Scheduling.
=> If Suppose Y ?P X.
=> If X can be solved in polynomial time, then Y can be solved in polynomial time.
=> Interval scheduling can be solved in polynomial time, so Independent Set can be solved in polynomial time.
=> Hence Independent Set is NP-complete.
=> If Suppose X is an NP-complete problem.
=> Then X is solvable in polynomial time if and only if P=NP.
=> So Independent Set being NP-complete and solvable in polynomial time imply P=NP.
=> ? P=NP. Independent Set is NP.
=> If P=NP, then Independent Set is P, i.e. Independent Set can be solved in polynomial time.
=> Hence the Independent Set ?P Interval Scheduling because Independent Set can be solved in polynomial time with a polynomial number of calls
to a black box that solves Interval Scheduling.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.