# Is there a relationship between time taken to reduce A to B and the time taken to solve B?

Example: If it takes $$O(n^2)$$ to solve A and it takes $$O(n^3)$$ to reduce A to B. So, it is certain that that B is at least as hard as A and takes at least $$O(n^2)$$ time to be solved.

Can we say something similar for reduction time and B such as B takes at least $$O(n^3)$$ time to be solved?

My thoughts: I think it has no relationship with the time complexity of B. However the reduction should be at most of polynomial time complexity otherwise, the reduction may not be possible practically. I do not have a proof for this as this point so, I'm unsure if this is correct. Any help is appreciated. Thank you.

• Any TM takes "at least $O(n^2)$" (or even $O(n^3)$) time to run since $0 \in O(n^2)$ and all TMs must run for a non-negative number of steps. You certainly want $\Omega$ here. – dkaeae Dec 5 '18 at 7:17