Problem Detail: 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?
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?
Asked By : 0xL33ch
Answered By : Denis
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 $Bleq_P A$ and $Ain NP$, then $Bin 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 $Bin EXPTIME$, since the NP oracle does not add power.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12397 3.2K people like this