Why one of NP-Complete problem had a polynomial solution then everyone of them has?

Question

Each NP problem is different, if one (even the hardest one) NP problem could be solved in polynomial time, I guess some related NP problems that could reduced to this one could also be solved in polynomial time. But why all? Does that mean all of other NP problems could be reduced to the one?

Answer 1

NP completeness means exactly that "all other NP problems could be reduced [in polynomial time] to the one", so yes, if a single NP-complete problem has a polynomial-time solution, then all NP problems do. See the formal definition.

Note that it is not obvious that NP-complete problems exist in the first place! E.g. maybe for every NP problem A, I can find an NP-problem B which is "polynomially harder" than A in the sense that there is no polytime-reduction from B to A. It turns out this isn't the case, but this takes proof. Some examples of NP-complete problems include:

• Determining whether a propositional formula is satisfiable.

• Determining whether a graph has a Hamiltonian path.

• Determining whether a graph can be $k$-colored.

And there are many others; see this list.

Answer 2

Because If one "NP-complete" problem can be solved without providing a general solution to the entire class of NP-complete problems, then the problem wasn't an NP-complete problem to begin with - by definition.