3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ the "non-NPCness" condition is not needed, you can remove it. $\endgroup$ – Kaveh Aug 16 '12 at 9:30
  • 2
    $\begingroup$ Reductions, whether polynomial time or other, do not "transform" an algorithm but compile one problem instance into an instance of another, on which the given algorithm can be (re)used. $\endgroup$ – Raphael Aug 16 '12 at 9:33
  • 1
    $\begingroup$ @Raphael: Alternatively, we can view a reduction from problem A to problem B as a way to transform an algorithm for problem B to an algorithm for problem A. Therefore, it is not correct to say “reductions do not ‘transform’ an algorithm.” These are just two different ways of describing the same fact. $\endgroup$ – Tsuyoshi Ito Aug 16 '12 at 12:26
4
$\begingroup$

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

  1. If $f$ is a polynomial, then $g(n)$ is also a polynomial,

  2. If $f(n) = 2^{\epsilon n}$, then $g(n) = 2^{\epsilon n^k}+p(n)$,

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

$\endgroup$

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.