# What does a polynomial time reduction mean?

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$?

• 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? – Mat.S Jul 31 '13 at 15:24

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.
• So the algorithm of $A$ in calling $B$ runs in polynomial time? – Mat.S Jul 31 '13 at 15:28
• 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. – Juho Jul 31 '13 at 15:29