0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ How did you create a $2^k$-sized problem in less than $2^k$ time? The reduction has to finish in polynomial time, so the output can be at most polynomially large. $\endgroup$
    – Craig Gidney
    Apr 8, 2016 at 20:06
  • 1
    $\begingroup$ This question can be answered by looking at the definition. Have you worked through the reference material yet? $\endgroup$
    – Raphael ♦
    Apr 9, 2016 at 9:36

3 Answers 3

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
2
$\begingroup$

First of all, for your definition of NP-complete, we require the reduction to be polynomial time. This makes it so that if we could solve an NP-complete language, L, in polynomial time, we would have a polynomial time algorithm for all of NP by composing the polynomial time reduction with that algorithm for L.

Note that the size of the output of a reduction has to be less than the run time of the reduction. The biggest output possible given a fixed run time would be one where a Turing machine, M, prints to its output tape at every step.

Improve this answer
$\endgroup$
0
$\begingroup$

The definition of P

does give its machines enough time to read the whole input, so we do
require that P reductions produce the whole output in a single execution
and
does not use parallelism, so P machines are unable to
output more bits than the amount of steps they run for

.


Thus, "the size of instance" after reduction is bounded above
by a polynomial in "the size of instance before reduction".

There are "reductions" from sufficiently-easy languages whose output size is always 1 bit:
For any target language L such that 1 is in L but 0 isn't, the "reduction"
can solve the input problem and then output 0 or 1 accordingly.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Sorry to bother, but you know, I am using mobile phone the most of the time, and I see comb-aligned text and multiple newlines, so it is kinda hard to read. $\endgroup$
    – Evil
    Apr 8, 2016 at 20:23
  • $\begingroup$ Downvoting because this is completely unreasonable formatting. $\endgroup$
    – Raphael ♦
    Apr 9, 2016 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.