<p><a href="http://iuuk.mff.cuni.cz/~koucky/papers/gap.pdf" rel="nofollow">Allender</a> suggests the answer is no:</p>

<blockquote>
  <p>There seems to be no pair of natural NP-complete problems A and B known, where a reduction from A to B is known to require more than linear time (even under the assumption that P $\ne$ NP)</p>
</blockquote>

<p>Reference:</p>

<p>E. Allender and M. Koucký, <a href="http://doi.acm.org/10.1145/1706591.1706594" rel="nofollow">Amplifying lower bounds by means of self-reducibility</a>. Journal of the ACM 57, 3, Article 14 (March 2010). </p>

CC BY-SA 3.0
2015-10-02T20:22:32.060Z
Could you please provide  a link to the paper where Allender writes this, or a reference?
Andras Farago
CC BY-SA 3.0
2015-10-02T20:24:14.823Z
@AndrasFarago  The link is provided. Click on Allender :).
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-10-02T21:29:14.777Z
Sorry, I missed the link. Having looked into the paper, I found another quite interesting statement: "no natural NP-complete problem is known to lie outside of NTIME(n)." (It is in the sentence immediately preceding the cited part.)
Andras Farago
CC BY-SA 3.0
2015-10-03T09:21:26.787Z
I suggest some mild discretion when interpreting these statements. There are some cases where only, say, a quadratic reduction is known. For example, a reduction to a planar version of a NP-complete problem may use a quadratic number of crossover gadgets. Lower bounds are tricky and lots of things are "not known to require".
Joe Bebel
CC BY-SA 3.0
2015-10-03T12:08:35.327Z
@AndrásSalamon Thanks for providing the link to the journal version.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-10-03T20:18:08.683Z
@JoeBebel I agree that discretion is needed when interpreting these statements. For example, in the statement that "no natural NP-complete problem is known to lie outside of NTIME(n)," the authors probably had a narrower interpretation of "natural" in mind. Perhaps they mean something like this: a natural problem is one that people may _really_ want to solve on the basis of practical motivation.
Andras Farago
CC BY-SA 3.0
2015-10-02T19:52:21.867Z
2015-10-03T12:07:55.353Z
2015-10-03T12:07:55.353Z
Mohammad Al-Turkistany
<p>When we want to prove that an $L\in \bf NP$ is $\bf NP$-complete, then the standard approach is to exhibit a polynomial time computable many-one reduction of a known $\bf NP$-complete problem to $L$. In this context we do not need a tight bound on the running time of the reduction. It suffices to have <em>any</em> polynomial bound, allowing that it may possibly have a very high degree. </p>

<p>Nevertheless, for natural problems, the bound is typically a <em>low degree</em> polynomial (let us define <em>low</em> as something in the single digits). I do not claim that this must always be the case, but I am not aware of a counterexample. </p>

<p><strong>Question:</strong> Is there a counterexample? That would be a polytime computable many-one reduction between two natural $NP$-complete problems, such that no no faster reduction is known for the same case, and the best known polynomial running time bound  is a <em>high degree</em> polynomial. </p>

<p><em>Note:</em> Large, or even huge, exponents are occasionally needed for natural problems in $P$, see 
<a href="https://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant">Polynomial-time algorithms with huge exponent/constant</a>. I wonder if the same also occurs in <em>reductions</em> among natural problems?</p>

CC BY-SA 3.0
2015-10-01T23:49:25.580Z
[This paper](ftp://athos.rutgers.edu/http/http/cs/pub/allender/stoc97.pdf) is possibly relevant. NP-completeness under very limited (eg AC0 or logspace) reductions is interesting, because most reductions are intuitively "gadget based", which stems from the fact that computation is a local phenomenon
Joe Bebel
CC BY-SA 3.0
2015-10-02T11:33:58.823Z
We usually deal with reductions that transform an instance of SAT (or a simple NPC problem) to an instance of $L$.  But thinking in the reverse way $L \leq_p SAT$ (i.e.-in the real world-try to solve a problem using a SAT solver) leads to polynomial time reductions with embarassing exponents :-). For example, a quite natural class of problems I'm familiar with, arises from PSPACE complete games, when you add some constraints (time, number of moves, limited visits to locations,...) that make them fall in NP, and then try to solve them with a SAT solver,i.e. find an *efficient* reduction to SAT.
Marzio De Biasi
CC BY-SA 3.0
2015-10-02T15:07:17.110Z
I remember we had a related question about natural NP problems which require large certificates (i.e. large proof complexity lower bounds) but I couldn't find it.
Kaveh
CC BY-SA 3.0
2015-10-02T16:01:42.503Z
@Kaveh: one is mine: "[Natural NP-complete problems with “large” witnesses](http://cstheory.stackexchange.com/q/27215/3247)" :-)
Marzio De Biasi
CC BY-SA 3.0
2015-10-02T18:15:17.927Z
By the hierarchy theorems there are problems in NP with nondeterministic time lower bounds that are polynomials of arbitrarily large degree.  Pick some problem that requires at least $n^d$ nondeterministic steps, for $d \ge 20$.  Suppose a many-one reduction from this problem to SAT exists that uses at most $n^c$ time.  Then the SAT instance can be no larger than $n^c$ bits.  This can then be decided using at most $n^{2c}$ nondeterministic steps.  Hence $c \ge d/2 \ge 10$.  If you want the problem to be natural as well, then you are essentially asking for natural problems not in NTIME($n^d$).
András Salamon
<cc.complexity-theory><reductions><np-complete>
Slowest many-one reduction?
Andras Farago
# Slowest many-one reduction?

(Asked by: username_0 on 2015-10-01)

When we want to prove that an $L\in \bf NP$ is $\bf NP$-complete, then the standard approach is to exhibit a polynomial time computable many-one reduction of a known $\bf NP$-complete problem to $L$. In this context we do not need a tight bound on the running time of the reduction. It suffices to have *any* polynomial bound, allowing that it may possibly have a very high degree.

Nevertheless, for natural problems, the bound is typically a *low degree* polynomial (let us define *low* as something in the single digits). I do not claim that this must always be the case, but I am not aware of a counterexample.

**Question:** Is there a counterexample? That would be a polytime computable many-one reduction between two natural $NP$-complete problems, such that no no faster reduction is known for the same case, and the best known polynomial running time bound is a *high degree* polynomial.

*Note:* Large, or even huge, exponents are occasionally needed for natural problems in $P$, see
[Polynomial-time algorithms with huge exponent/constant](https://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant). I wonder if the same also occurs in *reductions* among natural problems?

**Tags:** cc.complexity-theory, reductions, np-complete

> **Comments:**
> **username_1**: [This paper](ftp://athos.rutgers.edu/http/http/cs/pub/allender/stoc97.pdf) is possibly relevant. NP-completeness under very limited (eg AC0 or logspace) reductions is interesting, because most reductions are intuitively "gadget based", which stems from the fact that computation is a local phenomenon  
> **username_2**: We usually deal with reductions that transform an instance of SAT (or a simple NPC problem) to an instance of $L$.  But thinking in the reverse way $L \leq_p SAT$ (i.e.-in the real world-try to solve a problem using a SAT solver) leads to polynomial time reductions with embarassing exponents :-). For example, a quite natural class of problems I'm familiar with, arises from PSPACE complete games, when you add some constraints (time, number of moves, limited visits to locations,...) that make them fall in NP, and then try to solve them with a SAT solver,i.e. find an *efficient* reduction to SAT.  
> **username_3**: I remember we had a related question about natural NP problems which require large certificates (i.e. large proof complexity lower bounds) but I couldn't find it.  
> **username_2**: @username_3: one is mine: "[Natural NP-complete problems with “large” witnesses](http://cstheory.stackexchange.com/q/27215/3247)" :-)  
> **username_4**: By the hierarchy theorems there are problems in NP with nondeterministic time lower bounds that are polynomials of arbitrarily large degree.  Pick some problem that requires at least $n^d$ nondeterministic steps, for $d \ge 20$.  Suppose a many-one reduction from this problem to SAT exists that uses at most $n^c$ time.  Then the SAT instance can be no larger than $n^c$ bits.  This can then be decided using at most $n^{2c}$ nondeterministic steps.  Hence $c \ge d/2 \ge 10$.  If you want the problem to be natural as well, then you are essentially asking for natural problems not in NTIME($n^d$).  

---

## 1 answers

### Answer by username_5 on 2015-10-02. Score: 4

[Allender](http://iuuk.mff.cuni.cz/~koucky/papers/gap.pdf) suggests the answer is no:

> There seems to be no pair of natural NP-complete problems A and B known, where a reduction from A to B is known to require more than linear time (even under the assumption that P $\ne$ NP)

Reference:

E. Allender and M. Koucký, [Amplifying lower bounds by means of self-reducibility](http://doi.acm.org/10.1145/1706591.1706594). Journal of the ACM 57, 3, Article 14 (March 2010).

> **Comments:**
> **username_0**: Could you please provide  a link to the paper where Allender writes this, or a reference?  
> **username_5**: @AndrasFarago  The link is provided. Click on Allender :).  
> **username_0**: Sorry, I missed the link. Having looked into the paper, I found another quite interesting statement: "no natural NP-complete problem is known to lie outside of NTIME(n)." (It is in the sentence immediately preceding the cited part.)  
> **username_1**: I suggest some mild discretion when interpreting these statements. There are some cases where only, say, a quadratic reduction is known. For example, a reduction to a planar version of a NP-complete problem may use a quadratic number of crossover gadgets. Lower bounds are tricky and lots of things are "not known to require".  
> **username_5**: @AndrásSalamon Thanks for providing the link to the journal version.  
> **username_0**: @JoeBebel I agree that discretion is needed when interpreting these statements. For example, in the statement that "no natural NP-complete problem is known to lie outside of NTIME(n)," the authors probably had a narrower interpretation of "natural" in mind. Perhaps they mean something like this: a natural problem is one that people may _really_ want to solve on the basis of practical motivation.  

---

