Cheap and Secure Web Hosting Provider : See Now

[Solved]: Size of instance after reduction

, , No Comments
Problem Detail: 

A decision problem $C$ is $NP$-complete if $C$ is in $NP$, and every problem in $NP$ is reducible to $C$ in polynomial time.

Reduction means transforming an instance of one problem $A$ to an instance of another problem $B$, and by using an algorithm that solves $B$ we can obtain the solution to $A$ for our original instance.

Is there any relationship between the size of instance before and after reduction? If for example the algorithm solving $A$ is $O(n^2)$ and our instance of $A$ of size $n$, what can we say about the instance size after reducing it to $B$, whose algorithm is $O(2^n)$ (the complexity of algorithms actually doesn't matter). Is it $n$ as well? Or maybe it is a polynomial of $n$?

The question is if the fact that a problem $A$ can be reduced to $B$ in polynomial time tells us anything about the size of the resulting instance (of problem $B$) with respect to the size of initial instance of $A$.

Why? It is known that

If we had a polynomial algorithm for an $NP$-complete problem we could solve any other $NP$ problem in polynomial time

right? Because we just reduce $NP$ problem to $NP$-complete problem in polynomial time and solve it in polynomial time.

Let's say problem $A$ is $NP$ and problem $B$ is $NP$-complete. I've found an algorithm for $B$ that is $O(n)$ (polynomial). And let's say the size of our $A$ instance is $k$. If I reduced it to $B$ in polynomial time and got an instance of $B$ of size $n=2^k$, then the total time of solving it wouldn't be polynomial. So certainly the polynomial time reduction can't give an instance of size $2^k$, because if it could, then the quote above wouldn't be true.

Asked By : user4205580

Answered By : Raphael

The question is if the fact that a problem A can be reduced to B in polynomial time tells us anything about the size of the resulting instance (of problem B) with respect to the size of initial instance of A.

Yes, of course. If your reduction function $f$ has running-time function $T_f \in O(n^k)$, then $|f(x)| \in O(n^k)$ -- a Turing machine can not write to more than one cell per execution step.

Let's say problem A is NP and problem B is NP-complete. I've found an algorithm for B that is O(n) (polynomial).

Now you are rich, but go on.

And let's say the size of our A instance is k. If I reduced it to B in polynomial time and got an instance of B of size $n=2^k$

As explained above, that can not happen.

then the total time of solving it wouldn't be polynomial.

So what? Just because one reduction to one problem and using that one's algorithm does not yield a polynomial-time algorithm for $A$ does not imply that $A \not\in P$.

Plus, you never assume that $A \in P$ so there is very clearly no contradiction.

So certainly the polynomial time reduction can't give an instance of size $2^k$, because if it could, then the quote above wouldn't be true.

That statement is correct, but your reasoning is flawed as explained above.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55701

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback