0
$\begingroup$

I'm having trouble understanding reduction. Lets say you have a decision problem A that is NP-Complete. Also, another problem B the can be reduced from A.

What can you say about B if:

1) The reduction is done in polynomial time
2) The reduction is done in exponential time

I know that if A is reduced to B means that if we knew how to solve B, then solving A would be easy. But I don't understand what 1 & 2 signify.

Would it be right to say that for 1)
B is in the same Class as A

And for 2)
That B > then NP-Complete?

$\endgroup$
  • $\begingroup$ The notion "if A is reduced to B means that if we knew how to solve B, then solving A would be easy" is a bit simplistic. What happens if A is really hard, the language of B consists of only two elements TRUE and FALSE (and is therefore really easy), but one is allowed a really powerful machine to do the reduction? $\endgroup$ – András Salamon May 31 '13 at 13:59
2
$\begingroup$

In fact, depending on the class you want to reduce to, you need to be careful about the reduction you are doing.

For instance to preserve the class $P$, you need to do $LOGSPACE$-reductions. For the class $NP$, you need $P$-reductions.

I'm also afraid that you reverse the reductions: to show that a problem $B$ is in $NP$, you need to reduce it (polynomially) to a problem $A$ in $NP$. Meaning that if you to how to solve $A$ in $NP$, then you can solve $B$ by reducing it to $A$.

So to sum up, if $B\leq_P A$ and $A\in NP$, then $B\in NP$. Indeed the NP algorithm is clear: perform your reduction (polynomial time) and then solve the instance of $A$ you reduced to (in $NP$).

However, if the reduction is exponential, then we cannot say anything about $B$, except that it is in $EXPTIME^{NP}$, i.e. you can solve it in exponential time with an $NP$ oracle. It is in fact the same that just saying $B\in EXPTIME$, since the NP oracle does not add power.

$\endgroup$
  • $\begingroup$ Why do "you need P-reductions"? NP-complete can be defined using logspace (many-one) reductions, too (however this NP-complete may be different from the "usual" one). This aside, it's a good answer. $\endgroup$ – frafl May 31 '13 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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