# Can we reduce an NP to an NP Problem?

Lets say Problem A,B are in NP.

Can we reduce Problem A to B? Meaning A $≤_p$ B? or A $≤_t$ B

Is there a difference in "hardness" of a Problem even in NP?

Or must Problem B at least be NP-Complete?

• Google "NP completeness"! – xuq01 Jun 27 '18 at 5:01

## 2 Answers

It depends on the problems. Just knowing that $A$ and $B$ are in $NP$ doesn't tell you whether $A$ is reducible to $B$.

If $B$ is in $P$ and $A$ is $NP$-complete, then $A$ cannot be reduced to $B$ (unless $P=NP$).

If $A$ is in $P$ then it can be reduced to any problem $B$ except $\emptyset$ and $\Sigma^*$.

If $B$ is $NP$-complete then any problem (in $NP$) can be reduced to it.

• and if A is in NP and can be reduced to B, would mean B has to be NP-Complete? – simplesystems Jun 26 '18 at 19:05
• Not necessarily. Only if A is NP-hard and B is in NP. – Tom van der Zanden Jun 26 '18 at 19:29
• now im really confused say A $≤_p$ B How do you read that? I read that as A reduced to B ? Is that right ? Solving A by using B? And if A is in NP B has to be what at least? – simplesystems Jun 26 '18 at 19:54
• @simplesystems B could be anything. The problem is that if A is in NP, this does not preclude A being in P. In that case, we can reduce A to B (in polynomial time) by first solving it and then outputting a trivial instance of B. – Tom van der Zanden Jun 26 '18 at 20:15

Ladner's theorem tells us that if $A$ is non-trivial, $A <_m B$ and $B$ is in $NP$, then there is some $C$ with $A <_m C <_m B$. Note that $A <_m C$ means that $A$ is polytime many-one reducible to $C$, but not vice versa.

So not only are there different levels of hardness inside $NP$, provided that $P \neq NP$, but these levels are even dense (between any two levels is another level).

Provided that $P \neq NP$, we can also get plenty of incomparable problems inside $NP$.

• and where is C in your example? NP-Complete? – simplesystems Jun 27 '18 at 4:27
• Since $B \in NP$ and $C <_m B$, we see that $C$ is definitely not $NP$-complete. – Arno Jun 27 '18 at 8:29