I came across this question while studying for an exam:
T/F: Suppose we can show for some fixed $k$, an NP-complete problem P has a time $O(n^k)$ algorithm. Then every problem in NP has a $O(n^k)$ time algorithm.
I think the answer is false, since we can't reduce NP-complete to NP-hard in linear time, right? Or am I completely misunderstanding reductions/NP problems? Any help would be greatly appreciated. Thank you.