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?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
|
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$. |
|||
|
|
