1
$\begingroup$

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?

1 Answers 1

2

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$.