0

If A and B are in P and A can be polynomially reduced to B. Then can B be polynomially reduced to A? If yes then how?

Another way to think about it.

If A is NP-complete and B is in P and if A can be polynomially reduced to B then P=NP. it is stated that if P=NP then P=NP=NPC excluding the trivial languages in P. The empty set and the set of all strings.

Why does the fact that if all problem in NP can polynomially reduced to one problem in P imply that any problem in NP can be reduced to all problems in P?

Jonathan Kowalski
  • 3

1 Answers1

0

If $A$ and $B$ are in $\mathtt{P}$ then they are equivalent, so there is no need to reduce one to the other. Similarly all problems in $\mathtt{NP}$ are equivalent. So if we (in this case) reduce a problem in $\mathtt{NP}$ to one in $\mathtt{P}$, then all problems in $\mathtt{NP}$ follow suit.

JMP
  • 21,771