
> 
> **Question**:  
> 
>  is it known, whether there is an upper bound on the exponent of the fastest polynomial-time reduction from $\mathrm{3SAT}$ to $\mathrm{NP}$-$\mathrm{hard}$ 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 $\mathrm{3SAT}$? 
> 
> 
> 


Additional, secondary question:
Which $\mathrm{NP}$-$\mathrm{hard}$ problem requires the polynomial time reduction from $\mathrm{3SAT}$ with the highest exponent?



Naive question about polynomial time reducibility
It's unlikely there is any upper bound. To see the problem, consider the (artificial) problem


$\text{3SATpad} = \{ \phi \#^{|\phi|^{100}} : \phi \in \text{3SAT}\}$, 


where $\#$ is some new symbol. $\text{3SATpad}$ is in $\mathsf{NP}$, and there is an obvious $O(n^{100})$-time reduction from $\text{3SAT}$ to $\text{3SATpad}$. But it's doubtful there's even an $O(n^{99})$-time reduction. Otherwise, one could solve $\text{3SAT}$ 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 \#^{|\psi|^{100}}$, reject.
3. Otherwise, since $|\psi \#^{|\psi|^{100}}| \leq O(n^{99})$, it must be that $|\psi| \leq O(n^{.99})$. Now decide if $\psi \in \text{3SAT}$ 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 $\mathsf{P} \neq \mathsf{NP}$ (rather than on E.T.H.), by a Ladner's Theorem-type argument...


