CMI2019-A-8

Question

We have constructed a polynomial time reduction from problem A to problem B. Which of the following is not a possible scenario?

• A. We know of polynomial time algorithms for both A and B.
• B. We only know of exponential time algorithms for both A and B.
• C. We only know an exponential time algorithm for A, but we have a polynomial time algorithm for B.
• D. We only know an exponential time algorithm for B, but we have a polynomial time algorithm for A.

Answer 1

Ans (c)

Since, we have a polynomial time algorithm for $B$, the reduction of this will give us the polynomial time solution for the algorithm $A$.

So, it is not possible to have such a case where we $\textbf{only}$ have the exponential time for the algorithm of $A$

For more explain refer: https://gateoverflow.in/203287/cmi2017-a-10

Answer 2