in Theory of Computation recategorized by
625 views
0 votes
0 votes

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

  1. We know of polynomial time algorithms for both A and B.
  2. We only know of exponential time algorithms for both A and B.
  3. We only know an exponential time algorithm for A, but we have a polynomial time algorithm for B.
  4. We only know an exponential time algorithm for B, but we have a polynomial time algorithm for A.
in Theory of Computation recategorized by
by
625 views

2 Answers

0 votes
0 votes

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

by
0 votes
0 votes

Answer:

Answer:

Related questions