Return to Question

deleted 15 characters in body; edited title

Source Link

edited Jul 31, 2013 at 15:40

22.8k
7
62
117

Polytime Reduction (Meaning) What does a polynomial time reduction mean?

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

So for example suppose:

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

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

Then

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

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

Polytime Reduction (Meaning)

Sorry for this simple question but I am having a little trouble understanding what is meant by poly-time reduction? So 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 the algorithm that takes input as a list of numbers and returns whether there is a sublist whose sum is 0.

B is the algorithm that takes inout as a list of numbers, 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

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

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

Source Link

asked Jul 31, 2013 at 15:06

Mat.S

Polytime Reduction (Meaning)

So for example suppose

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

B is the algorithm that takes inout as a list of numbers, 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

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

time-complexity reductions