Mfcttrf

Question:

is it known, whether there is an upper bound on the exponent of the fastest polynomial-time reduction from $mathrm3SAT$ to $mathrmNP$-$mathrmhard$ problems or, can it be proved that for every problem requiring an $Theta(n^k)$ time reduction, there is a problem requiring an $Omega(n^k+1)$ reduction from $mathrm3SAT$?

Additional, secondary question:
Which $mathrmNP$-$mathrmhard$ problem requires the polynomial time reduction from $mathrm3SAT$ with the highest exponent?

It's unlikely there is any upper bound. To see the problem, consider the (artificial) problem

$text3SATpad = phi #^ : phi in text3SAT$,

where $#$ is some new symbol. $text3SATpad$ is in $mathsfNP$, and there is an obvious $O(n^100)$-time reduction from $text3SAT$ to $text3SATpad$. But it's doubtful there's even an $O(n^99)$-time reduction. Otherwise, one could solve $text3SAT$ in $2^O(n^.99)$ time (unlikely, as this violates the Exponential Time Hypothesis), as follows:

1. On input $phi$ of length $n$, run the reduction producing string $y$. The key point here is that $|y| leq O(n^99)$.




2. If $y$ is not of the form $psi #^$, reject.




3. Otherwise, since $|psi #^| leq O(n^99)$, it must be that $|psi| leq O(n^.99)$. Now decide if $psi in text3SAT$ in $2^O(n^.99)$ time, using a naive brute-force algorithm. This gives the correct answer about satisfiability of $phi$.

Perhaps one can even prove the impossibility conditioned only on $mathsfP neq mathsfNP$ (rather than on E.T.H.), by a Ladner's Theorem-type argument...