All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?

My book states this

• If a decision problem B is in P and

A reduces to B,
then decision problem A is in P.

• A decision problem B is NP-complete if

B is in NP and
for every problem in A in NP, A reduces to B.

• A decision problem C is NP-complete if

C is in NP and
for some NP-complete problem B, B reduces to C.


So my questions are

• If B or C is in NP-complete, and all problems in NP reduce to an NP-complete problem, using the first rule, how can any NP problem not be NP complete?

• If A reduces to B, does B reduce to A?

If A reduces to B, does B reduce to A?

No. For a really contrived example, any possible computable problem A is reducible to the Halting Problem: just pass as input the algorithm that solves the problem A but with a while(true) tacked at the end after either the true or false case. However, we know that the Halting problem isn't computable so it can't be reduced to any such algorithm A.

The basic idea is that if there is a reduction from A to B you can learn that B is at least as hard to solve then A and requires an algorithm that is at least as powerful.

So if a problem A reduces to an easy problem B, then we can deduce A is easy (since the reduction gives us the efficient algorithm) and if a hard problem A reduced to a problem B, we can deduce that B is also hard (since if B were easy then A would have to be easy too). However there is still the possibility of making a silly reduction from an easy problem to a hard problem but in this case we can't deduce any conclusions.

StackExchange Computer Science Q#1526, answer score: 14