1
$\begingroup$

I am having a little trouble understanding what is meant by a poly-time reduction. Suppose I have two algorithms $A$ and $B$ and then I say that $A$ is reducible to $B$. Does polytime reduction mean that the algorithm that solves $A$ using $B$ as a helper runs in $O(n^k)$ for some $k$?

So for example suppose:

$A$ is an algorithm that takes as input a list of numbers and returns whether there is a sublist whose sum is $0$.

$B$ is an algorithm that takes as input a list of numbers, and an integer $k$, and returns whether there is a sublist of length $k$ whose sum is $0$.

Then

def A(L):
     for i in range (1, len(L)+1)"
           if B(L, i):
                return true
     return false

Since this $A$ calling $B$ as a helper runs in $O(n)$ so can this be described as a polytime reduction from $A$ to $B$?

$\endgroup$
  • $\begingroup$ Ok so in my case I am given a $B$ which performs the specified task. And then for $A$ I call $B$ as a helper to repeatedly perform this task and the running time for $A$ is $O(n)$. So as long as the running-time of $A$ is polynomial, then the entire process can be described as a polytime reduction? $\endgroup$ – Mat.S Jul 31 '13 at 15:24
2
$\begingroup$

Be careful, you probably mean a reduction from a problem to another, and not a reduction from an algorithm to another.

When a problem $A$ is polynomial time reducible to a problem $B$, it means that given an instance of $A$, there is an algorithm for transforming instances of $A$ into instances of $B$. This is often done to derive hardness results: if there was a fast algorithm for some problem, there would also be a fast algorithm for some other problem. The Wikipedia article on reductions gives as an example problem pair multiplication and squaring. Both of these happen to be rather easy problems, of course.

It doesn't matter what your problems look like and how the transformation actually works, as long as it is both correct and polynomial time.

$\endgroup$
  • $\begingroup$ So the algorithm of $A$ in calling $B$ runs in polynomial time? $\endgroup$ – Mat.S Jul 31 '13 at 15:28
  • $\begingroup$ Maybe we don't know of an algorithm for solving $A$. But because we can transform instances of it into $B$, and we already have an algorithm for $B$, we can solve instances of $A$. The transformation works in polynomial time. You might want to look at Turing reductions too. $\endgroup$ – Juho Jul 31 '13 at 15:29

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.