Computationally 'hard' polynomial-time reduction to other NP-complete problems / Hierarchy of NP-complete problems
There are no upper bounds on the complexity of polynomial-time reductions between $\mathrm{NP}$-complete problems, other than that they're in polynomial time.

Let $\mathrm{NP}_k = \mathrm{NTIME}[O(n^k)]\setminus\mathrm{NTIME}[O(n^{k-1})]$. By the nondeterministic version of the time hierarchy theorem, there are problems in $\mathrm{NP}_k$, for all $k$.

Let $X$ be any $\mathrm{NP}$-complete problem. There is some $t$ such that $X\in\mathrm{NTIME}[n^t]$.  Consider some problem $L\in\mathrm{NP}_k$ for some $k&gt;t$.  If we have a reduction from $L$ to&nbsp;$X$ that runs in time&nbsp;$n^r$, then we can solve an instance of&nbsp;$L$ in time&nbsp;$O(n^{rt})$ by first running the reduction, which creates an $X$-instance of length&nbsp;$O(n^r)$, and then solving that instance in time&nbsp;$O((n^r)^t)$.  This contradicts the nondeterministic time hierarchy theorem if $k&gt;rt$.