There are problems A and B in NP. Problem A polynomially transforms to problem B. Suppose A is in P. Is it correct to state that this teaches us nothing new about problem B?
2026-04-09 13:00:21.1775739621
Polynomial transform (P, NP)
122 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
It's correct to say that this teaches us nothing new about problem $B$ if all we know is what you've written. If we know a lower bound for the complexity of $A$, then polynomially transforming $A$ to $B$ does give us a lower bound for the complexity of $B$.