Computationally 'hard' polynomial-time reduction to other NP-complete problems / Hierarchy of NP-complete problems

2017-10-17 08:25:45

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

Question: Are there NP-complete problems with a large best known (deterministic?) polynomial-time reduction?

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

  • The graph of known 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.

    2017-10-17 08:43:58