patternMinor
Computationally 'hard' polynomial-time reduction to other NP-complete problems / Hierarchy of NP-complete problems
Viewed 0 times
computationallypolynomialhierarchyhardproblemstimecompletereductionother
Problem
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}$.
(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?)
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 (non-special-tailored) 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 one NP-complete problem mean a polynomial time algorithm for all NP-complete problems?)
Solution
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$.
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$.
Context
StackExchange Computer Science Q#82598, answer score: 6
Revisions (0)
No revisions yet.