I discover this in All NP problems reduce to NP-complete problems: so how can NP problems not be NP-complete?
- If problem B is in P and A reduces to B, then problem A is in P.
- Problem B is NP-complete if B is in NP and for every problem in A in NP, A reduces to B.
- Problem C is NP-complete if C is in NP and for some NP-complete problem B, B reduces to C.
My questions are (if I then II then(?) III/I. If III/I and III/II then IV.)
- I: Are there a generalized form to reduces NP problem to either P or NP-complete?
- II: Are there a certain number of NP-complete problems?
- III/I: Are all of the NP-complete problems can be reduces to all other NP-problems?
- III/II: If we can reduce B in NP-complete problem to A in P, can we prove that all problem reduces to B is in P?
- IV: If we prove that there is an NP-complete problem that is P, Can we consider that P=NP?