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

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.

Tags:

Np Complete