The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+1 vote

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

- If the best algorithm for $B$ takes exponential time, then there is no polynomial time algorithm for $A$
- If the best algorithm for $A$ takes exponential time, then there is no polynomial time algorithm for $B$.
- If we have a polynomial time algorithm for $A$, then we must also have a polynomial time algorithm for $B$
- If we don’t know whether there is a polynomial time algorithm for $B$, then there cannot be a polynomial time algorithm for $A$.

+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)$).

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 487
- Exam Queries 436
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,194 questions

43,647 answers

124,088 comments

42,928 users