The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
183 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$.
asked in Algorithms by Boss (16.6k points)
edited by | 183 views

1 Answer

+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)$).
answered by Boss (16.6k points)
edited by

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,779 questions
46,781 answers
140,753 comments
58,681 users