patternMinor
Can an exponential algorithm for an NPC problem be transformed into an algorithm for other NP problems in polynomial time?
Viewed 0 times
problemcantransformedpolynomialexponentialnpcintoproblemstimealgorithm
Problem
After looking at other questions and my textbook, I seem to get some confusion.
I do get that when there is a polynomial algorithm of NPC, there is a polynomial algorithm for a NP problem.
But the statement describing reduction seems obscure to me at least in the beginning of my studies in computational complexity.
So, can we transform an exponential algorithm for NPC (which we have) into an exponential algorithm for another non-NPC NP problem in polynomial time?
I do get that when there is a polynomial algorithm of NPC, there is a polynomial algorithm for a NP problem.
But the statement describing reduction seems obscure to me at least in the beginning of my studies in computational complexity.
So, can we transform an exponential algorithm for NPC (which we have) into an exponential algorithm for another non-NPC NP problem in polynomial time?
Solution
If you have an algorithm running in time $f(n)$ that solves an $\mathsf{NP\text{-}complete}$ problem, you can use it to solve any $\mathsf{NP}$ problem and the running time will be $g(n)=f(n^k) + p(n)$ ($k$ is a constant which depends on the reduction between the problems, $p(n)$ is a polynomial essentially giving the running time of the reduction function).
I am not sure what you mean exactly by exponential time, but the result above is general and will work for any $f$, e.g.:
-
If $f$ is a polynomial, then $g(n)$ is also a polynomial,
-
If $f(n) = 2^{\epsilon n}$, then $g(n) = 2^{\epsilon n^k}+p(n)$,
-
If $f(n)= 2^{n^\epsilon}$ then $g(n) = 2^{n^{k\epsilon}}+p(n)$.
I am not sure what you exactly mean by transforming an algorithm, but
what is essentially needed is that we are given a reduction algorithm from $Q'$ to $Q$. If we have that, it is easy to compose it with any algorithm $A$ for $Q$ to obtain an algorithm for $Q'$.
If this is given as an input to the transformation, it can transform an algorithm $A$ for $Q$ to an algorithm for $Q'$ very easily (in polynomial time): it will output the code resulting from composing the code for the reduction from $Q'$ to $Q$ with the code for the algorithm $A$. In fact, this can be done in linear time.
If the reduction is not given as an input then the algorithm has to find it. It can be done under some conditions but essentially we have to provide the transformation with enough information so that the transformation can find the needed reduction algorithm. If we don't provide enough information to find the reduction then this cannot be done. At least not uniformly in $A$. Here is an argument:
The transformation has to return an algorithm that is essentially the composition of a reduction function from $Q'$ to $Q$ with $A$. However the transformation cannot check what a given algorithm $A$ for $Q$ is really doing (because of Rice's theorem). So we can give an identity algorithm as $A$ and the transformation will not notice this and will return an algorithm which is essentially the composition of a reduction from $Q'$ to $Q$ with the identity function. But that is equal to the reduction function from $Q'$ to $Q$. So the output will be a reduction algorithm from $Q'$ to $Q$.
I am not sure what you mean exactly by exponential time, but the result above is general and will work for any $f$, e.g.:
-
If $f$ is a polynomial, then $g(n)$ is also a polynomial,
-
If $f(n) = 2^{\epsilon n}$, then $g(n) = 2^{\epsilon n^k}+p(n)$,
-
If $f(n)= 2^{n^\epsilon}$ then $g(n) = 2^{n^{k\epsilon}}+p(n)$.
I am not sure what you exactly mean by transforming an algorithm, but
what is essentially needed is that we are given a reduction algorithm from $Q'$ to $Q$. If we have that, it is easy to compose it with any algorithm $A$ for $Q$ to obtain an algorithm for $Q'$.
If this is given as an input to the transformation, it can transform an algorithm $A$ for $Q$ to an algorithm for $Q'$ very easily (in polynomial time): it will output the code resulting from composing the code for the reduction from $Q'$ to $Q$ with the code for the algorithm $A$. In fact, this can be done in linear time.
If the reduction is not given as an input then the algorithm has to find it. It can be done under some conditions but essentially we have to provide the transformation with enough information so that the transformation can find the needed reduction algorithm. If we don't provide enough information to find the reduction then this cannot be done. At least not uniformly in $A$. Here is an argument:
The transformation has to return an algorithm that is essentially the composition of a reduction function from $Q'$ to $Q$ with $A$. However the transformation cannot check what a given algorithm $A$ for $Q$ is really doing (because of Rice's theorem). So we can give an identity algorithm as $A$ and the transformation will not notice this and will return an algorithm which is essentially the composition of a reduction from $Q'$ to $Q$ with the identity function. But that is equal to the reduction function from $Q'$ to $Q$. So the output will be a reduction algorithm from $Q'$ to $Q$.
Context
StackExchange Computer Science Q#3216, answer score: 4
Revisions (0)
No revisions yet.