+1 vote
49 views
We have constructed a polynomial time reduction from problem A to problem B. Which of the following is a valid inference?

(a) If the best algorithm for B takes exponential time, there is no polynomial time algorithm for A

(b) If the best algorithm for A takes exponential time, there is no polynomial time algorithm for B.

(c) If we have a polynomial time algorithm for A, we must also have a polynomial time algorithm for B.

(d) If we don’t know whether there is a polynomial time algorithm for B, there cannot be a polynomial time algorithm for A.

A is reducible to B implies B is as tough as A. ( A cannot be harder then B)

Option A - False if A is polynomial then B must be Polynomial ( A polynomial algorithm can be easily converted into exponential converse is not true)

Option B- True as per first line above if A is expositional then B cannot be a polynomial time

Option C - False If we have polynomial time algorithm for A then we can polynomial, expositional, sub expositional algorithm for B

Option D- False A can be polynomial B can be more harder then polynomial ( as per 1st line B is as hard as a can be termed as B=$\Omega$(A))