# Naive question about polynomial time reducibility

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?

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...

• Can’t you prove it unconditionally using the nondeterministic time hierarchy theorem? – Emil Jeřábek supports Monica Sep 29 at 17:44
• Seems possible, yes. – Ryan O'Donnell Sep 29 at 17:50
• On second thoughts, it may not be so easy. The assumption that 3SAT reduces to any NP-complete language in $O(n^k)$ time implies (and is, in fact, equivalent to) that for every $L\in\mathrm{NP}$ and every constant $c$, $L$ can be decided by a deterministic polynomial-time computation (with exponent only depending on $L$) followed by an $O(n^{1/c})$-time nondeterministic computation. However, I couldn’t get this to contradict the nondeterministic time hierarchy theorem. – Emil Jeřábek supports Monica Sep 30 at 15:26