My book states this If a decision problem B is in P and A reduces to B, then dec

Question

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?

Explanation / Answer

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.

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.