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

| cite | improve this answer | |
  • 3
    $\begingroup$ Can’t you prove it unconditionally using the nondeterministic time hierarchy theorem? $\endgroup$ – Emil Jeřábek Sep 29 '19 at 17:44
  • $\begingroup$ Seems possible, yes. $\endgroup$ – Ryan O'Donnell Sep 29 '19 at 17:50
  • 1
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek Sep 30 '19 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.