As we all know there exist plenty of polynomial-time reductions from one NP-complete problem to another. Are there any NP-complete problems that have a rather large polynomial bound for reductions to other NP-complete problems, like a poly-time sub-hierarchy of NP-complete problems...?

E.g. lets assume I have NP-complete problem A and B. They are reducible to each other in lets say at most $n^3$. Does there exist a NP-complete problem such that the best known reduction to both A and B (and all other) is, lets say, $n^{100}$.

  1. Question: Are there (non-special-tailored) NP-complete problems with a large best known (deterministic?) polynomial-time reduction?
  2. Question: Is there a upper (deterministic?) polynomial bound for polynomial-time reductions between NP-complete problems

(There is a question here asking for a hierarchy of NP-complete problems but with a different base-problem, so solution does not really answer my question: Understanding reductions: Would a polynomial time algorithm for one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?)


There are no upper bounds on the complexity of polynomial-time reductions between $\mathrm{NP}$-complete problems, other than that they're in polynomial time.

Let $\mathrm{NP}_k = \mathrm{NTIME}[O(n^k)]\setminus\mathrm{NTIME}[O(n^{k-1})]$. By the nondeterministic version of the time hierarchy theorem, there are problems in $\mathrm{NP}_k$, for all $k$.

Let $X$ be any $\mathrm{NP}$-complete problem. There is some $t$ such that $X\in\mathrm{NTIME}[n^t]$. Consider some problem $L\in\mathrm{NP}_k$ for some $k>t$. If we have a reduction from $L$ to $X$ that runs in time $n^r$, then we can solve an instance of $L$ in time $O(n^{rt})$ by first running the reduction, which creates an $X$-instance of length $O(n^r)$, and then solving that instance in time $O((n^r)^t)$. This contradicts the nondeterministic time hierarchy theorem if $k>rt$.

  • $\begingroup$ Thanks a lot that's a nice answer to Question 2. Any idea on Question 1? $\endgroup$ – Marcel Tiepelt Oct 17 '17 at 23:35
  • $\begingroup$ @MarcelTiepelt Isn't it implicit? Pick any problem in what I've called $\mathrm{NP}_{1000}$. Any reduction from it to $\mathsf{3-Sat}$ takes time at least $n^{500}$. $\endgroup$ – David Richerby Oct 18 '17 at 7:26
  • $\begingroup$ Yes, sure. I guess I was not specific enough in my question. Does anyone know of any (non-special-tailored) NP-complete problem, with such an offset? $\endgroup$ – Marcel Tiepelt Oct 19 '17 at 0:01
  • $\begingroup$ @DavidRicherby, To have a perfect answer, you should replace $3SAT$ by an arbitrary $NP$-complete problem. This would falsify the existence of any $NP$-complete problem that has fixed polynomial-time reductions from all $NP$ problems. $\endgroup$ – Thinh D. Nguyen Sep 26 '18 at 14:15
  • $\begingroup$ @ThinhD.Nguyen Fair point. Done. $\endgroup$ – David Richerby Sep 26 '18 at 14:30

The graph of explicitly described reductions between NP-complete problems looks a lot more like a tree than a complete graph. So for most pairs of NP-complete problems the best known reduction follows a rather long path through that tree. Due to the blowup at each step I doubt that you'd want to implement the resulting reductions.

I doubt that there is an upper bound on the reduction size. You surely can come up with artificial problems that are very difficult to reduce to, say, SAT. I'm not aware of any family of problems with known (increasing) lower bounds for reductions though.

  • $\begingroup$ Being a complete graph is unlikely? Is it the Berman-Hartmanis conjecture? $\endgroup$ – rus9384 Oct 17 '17 at 7:08
  • $\begingroup$ Taking the longest path in the tree one might find 2 problems that are hard to reduce to each other. But is there a problem such that the reduction to any problem (neighbor in the tree) is rather 'hard'? $\endgroup$ – Marcel Tiepelt Oct 17 '17 at 7:14
  • 1
    $\begingroup$ @rus9384 Normally the reductions are not isomorphisms, so the Berman-Hartmanis conjecture isn't relevant. For normal polytime reductions the graph is complete by definition. $\endgroup$ – adrianN Oct 17 '17 at 7:51
  • 1
    $\begingroup$ The graph of reductions between NP-complete problems is a complete graph, by definition. $\endgroup$ – David Richerby Oct 17 '17 at 8:37
  • $\begingroup$ @DavidRicherby Of course, but the graph of reductions that someone has written down isn't. So for most pairs of problems the best "known" reduction is created by plugging together the reductions along a path on that sparse graph of known reductions. $\endgroup$ – adrianN Oct 17 '17 at 9:50

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.