edited by
2,291 views
3 votes
3 votes

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 by

2 Answers

3 votes
3 votes
$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)$).

Correct Answer: $B$
edited by
Answer:

Related questions