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?