What is the implication of the sentence: "if any NP complete problem is p time solvable, then all problems in NP are p time solvable"

I find this quote here on page 13


Does it mean that out of all different problems that are NP complete, if any problem is found to have a p time solution, then all the NP complete problems are p time solvable?

This is very unbelievable to me since NP complete problems are so different in nature and comes in a variety of form such as longest path, dominating vertex, halting problem, knapsack problem. Can someone show me how this statement is true?

This statement means exactly what you have said: if any NP-complete problem is solvable in polynomial time, then all of them are. This follows from the definitions: a problem X is NP-complete if all problems in NP are polynomial time reducible to it, that is, if for any problem Y in NP there is a polynomial time function $f_Y$ such that for all $w$, $w \in Y$ iff $f_Y(w) \in X$. Now suppose that you could solve X in polynomial time using some algorithm A. For any NP problem Y, you can use $f_Y$ in conjunction with A to solve Y in polynomial time.

This is indeed surprising, and it is one reason why most researchers conjecture that NP is different from P: otherwise all these disparate problems will have polynomial time solutions.

StackExchange Computer Science Q#33754, answer score: 3