For the purposes of this problem, you should not assume anything other than what

Question

For 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. 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

Solution:

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

False
Since there is a polynomial time reduction of vertex cover to independent set and vertex cover cannot be solved in polynomial time.

We can be sure since the independent set problem is a not a polynomial time algorithm.

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

False

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

True.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects