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
    Commented Dec 5, 2018 at 7:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.