contestada

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 ≤P Vertex Cover? (b) Question: Is it the case that Independent Set ≤P Interval Scheduling?

Respuesta :

temmydbrain

Answer:

Check the explanation

Explanation:

a) The answer B yes

• Because the greedy algorithm has used to perform the calculation of interval scheduling problem such as 0(n log n)

• In this interval scheduling process can be am in polynomial time without use the block box solves the vertex cover problem

• such that interval scheduling algorithm has solved o the polynomial computation process steps and add a polynomial number of call so black box test solvers of vertex cover

Sp therefore Interval Scheduling ≤P Vertex Cover

B)

The answer is unknown because it resolve the question has P=NP Proof:

• Independent set  ≤P interval scheduling

• such that Y<PX value can M solved to the NP time then it can M solved y value in polynomial value

• use the interval schedule process can be solve polynomial time

• such the independent set(IS) has to solve the polynomial time process_ therefore independent set is NP complete process

• If and only if condition has P=NP to polynomial time of x solvable

• use P=NP has the IS is NP

• If P=NP has independent set SP interval scheduling

• Because independent set can M solved to NP to the polynomial number of process call have to be test in black box to solve the interval schedule.

Otras preguntas