Reducibility

Question

State which are TRUE and which are FALSE (Question 1) and 2) both have same options)

$1)$If there is an algorithm for polynomial time reduction from A to B?

$2)$ if there is an algorithm for exponential time reduction from A to B?

Consider the following cases

$a)$ If A can have an exponential time algorithm then B also can have exponential time algo

$b)$ If B can have an polynomial time algorithm then A can have exponential time algo

$c)$ If  B can have an exponential time algorithm then A can have polynomial time algo

$d)$ A can have an polynomial time algorithm then B can have polynomial time algo

Comments

Deepanshu

The definition is there in Coreman. You just need to understand it properly or else you can refer to notes of Stanford or Berkeley

---

can u provide some reference too? or some good link

---

https://gateoverflow.in/71228/reducibility