+1 vote
196 views

We have constructed a polynomial time reduction from problem $A$ to problem $B$. Which of the following is a valid inference?

1. If the best algorithm for $B$ takes exponential time, then there is no polynomial time algorithm for $A$
2. If the best algorithm for $A$ takes exponential time, then there is no polynomial time algorithm for $B$.
3. If we have a polynomial time algorithm for $A$, then we must also have a polynomial time algorithm for $B$
4. If we don’t know whether there is a polynomial time algorithm for $B$, then there cannot be a polynomial time algorithm for $A$.
edited | 196 views

$A$ is reducible to $B$ implies $B$ is as tough as $A$. ($A$ cannot be harder than $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 have polynomial, expositional, sub expositional algorithm for $B$.

Option $D$- False. $A$ can be polynomial. $B$ can be harder than polynomial ( as per first line, $B$ is as hard as $A$ can be termed as $B=\Omega(A)$).