4
$\begingroup$

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?)

$\endgroup$

2 Answers 2

6
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Thanks a lot that's a nice answer to Question 2. Any idea on Question 1? $\endgroup$ Oct 17, 2017 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$ Oct 18, 2017 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$ Oct 19, 2017 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$ Sep 26, 2018 at 14:15
  • $\begingroup$ @ThinhD.Nguyen Fair point. Done. $\endgroup$ Sep 26, 2018 at 14:30
0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Being a complete graph is unlikely? Is it the Berman-Hartmanis conjecture? $\endgroup$
    – rus9384
    Oct 17, 2017 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$ Oct 17, 2017 at 7:14
  • 2
    $\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, 2017 at 7:51
  • 2
    $\begingroup$ The graph of reductions between NP-complete problems is a complete graph, by definition. $\endgroup$ Oct 17, 2017 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, 2017 at 9:50

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.