Computationally 'hard' polynomial-time reduction to other NP-complete problems / Hierarchy of NP-complete problems

Question

As we all know there exist plenty of polynomial-time reductions from one NP-complete problem to another. Are there any NP-complete problems that have a rather large polynomial bound for reductions to other NP-complete problems, like a poly-time sub-hierarchy of NP-complete problems...?

E.g. lets assume I have NP-complete problem A and B. They are reducible to each other in lets say at most $n^3$. Does there exist a NP-complete problem such that the best known reduction to both A and B (and all other) is, lets say, $n^{100}$.

1. Question: Are there (non-special-tailored) NP-complete problems with a large best known (deterministic?) polynomial-time reduction?
2. Question: Is there a upper (deterministic?) polynomial bound for polynomial-time reductions between NP-complete problems

(There is a question here asking for a hierarchy of NP-complete problems but with a different base-problem, so solution does not really answer my question: Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?)

Answer 1

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>t$. If we have a reduction from $L$ to $X$ that runs in time $n^r$, then we can solve an instance of $L$ in time $O(n^{rt})$ by first running the reduction, which creates an $X$-instance of length $O(n^r)$, and then solving that instance in time $O((n^r)^t)$. This contradicts the nondeterministic time hierarchy theorem if $k>rt$.

Answer 2

The graph of explicitly described reductions between NP-complete problems looks a lot more like a tree than a complete graph. So for most pairs of NP-complete problems the best known reduction follows a rather long path through that tree. Due to the blowup at each step I doubt that you'd want to implement the resulting reductions.

I doubt that there is an upper bound on the reduction size. You surely can come up with artificial problems that are very difficult to reduce to, say, SAT. I'm not aware of any family of problems with known (increasing) lower bounds for reductions though.