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.

  • $\begingroup$ 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. $\endgroup$ – dkaeae Dec 5 '18 at 7:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.