What does a polynomial time reduction mean?

Question

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

Answer 1

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.