12
$\begingroup$

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. I wonder if the same also occurs in reductions among natural problems?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ This paper 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 $\endgroup$
    – Joe Bebel
    Oct 1, 2015 at 23:49
  • 3
    $\begingroup$ 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. $\endgroup$
    – Marzio De Biasi
    Oct 2, 2015 at 11:33
  • $\begingroup$ 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. $\endgroup$
    – Kaveh
    Oct 2, 2015 at 15:07
  • 1
    $\begingroup$ @Kaveh: one is mine: "Natural NP-complete problems with “large” witnesses" :-) $\endgroup$
    – Marzio De Biasi
    Oct 2, 2015 at 16:01
  • 3
    $\begingroup$ 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$). $\endgroup$
    – András Salamon
    Oct 2, 2015 at 18:15

1 Answer 1

Reset to default
3
$\begingroup$

Allender 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. Journal of the ACM 57, 3, Article 14 (March 2010).

Improve this answer
$\endgroup$
6
  • $\begingroup$ Could you please provide a link to the paper where Allender writes this, or a reference? $\endgroup$
    – Andras Farago
    Oct 2, 2015 at 20:22
  • 1
    $\begingroup$ @AndrasFarago The link is provided. Click on Allender :). $\endgroup$
    – Mohammad Al-Turkistany
    Oct 2, 2015 at 20:24
  • $\begingroup$ 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.) $\endgroup$
    – Andras Farago
    Oct 2, 2015 at 21:29
  • 5
    $\begingroup$ 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". $\endgroup$
    – Joe Bebel
    Oct 3, 2015 at 9:21
  • 1
    $\begingroup$ @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. $\endgroup$
    – Andras Farago
    Oct 3, 2015 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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