Forr the purposes of this problem, you should not assume anything other than wha

Question

Forr the purposes of this problem, you should not assume anything other than what is stated in the problem. For example, you should not assume that the Vertex Cover problem or the Independent Set problem is in NP or is NP-hard.

(a) Suppose we knew that:

• there is a polynomial-time reduction from Vertex Cover to Independent Set and

• the Vertex Cover Problem can be solved in polynomial time.

With these assumptions, indicate which of the following choices is the right one (you don’t have to give any explanations.)

1. We know for sure that Independent Set can be solved in polynomial time.

2. We know for sure that Independent Set can’t be solved in polynomial time.

3. We can’t say for sure whether or not Independent Set can be solved in polynomial time.

(b) Suppose we knew that:

• there is a polynomial-time reduction from Vertex Cover to Independent Set and

• the Vertex Cover problem cannot be solved in polynomial time.

With these assumptions, indicate which of the following choices is the right one (you don’t have to give any explanations.)

1. We can’t say for sure whether or not Independent Set can be solved in polynomial time.

2. We know for sure that Independent Set can be solved in polynomial time.

3. We know for sure that Independent Set can’t be solved in polynomial time.

Explanation / Answer

(a)

As in polynomial time we can reduce the vertex cover problem to independent set problem.
We know that the vertex cover problem can be solved in polynomial time.

So if we can reduce problem X to Y in polynomial time So it means X is as hard Y problem So if we can solve X then we can solve problem Y also.

1. We know for sure that Independent Set can be solved in polynomial time.

(b)
if we can reduce problem X to Y in polynomial time So it means X is as hard Y problem So if we can solve X then we can solve problem Y also.

3. We know for sure that Independent Set can’t be solved in polynomial time.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.