# Exponential reduction vs Polynomial Reduction

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?

• 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? May 31 '13 at 13:59

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.

• 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. May 31 '13 at 17:25
• Is $EXPTIME^{NP}$ not at least $NEXPTIME$, which IIRC isn't known to be $EXPTIME$?
– l4m2
Dec 18 '19 at 17:18