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?

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

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.

  • $\begingroup$ and if A is in NP and can be reduced to B, would mean B has to be NP-Complete? $\endgroup$ – simplesystems Jun 26 '18 at 19:05
  • $\begingroup$ Not necessarily. Only if A is NP-hard and B is in NP. $\endgroup$ – Tom van der Zanden Jun 26 '18 at 19:29
  • $\begingroup$ 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? $\endgroup$ – simplesystems Jun 26 '18 at 19:54
  • $\begingroup$ @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. $\endgroup$ – 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$.

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

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.