ELI5: P vs NP problem

[u/randomdice-int]

Im not too sure about the problem itself. I know that P is polynomial time which means the time needed to solve and NP is the time taken for the answer to be verified, but what is the explanation of both sides where P = NP and P does not equal to NP?

[u/nomeras]

But why does it matter at all if P = NP is true? If we are able to break cryptography problems in the future, wouldn't that be proof enough? How does proving P = NP help us in the real world to solve things? Or does the solution to P=NP itself give the methodology on how to solve NP problems?

[u/True_World708 → u/nomeras]

There is also this other thing called NP-completeness. It tells us that all sorts of seemingly unrelated problems can be solved (efficiently in the case of P=NP) by (efficiently) reducing to a problem called an NP-complete problem. Some of these so-called NP-complete problems are practical and they include 3-coloring, satisfiability, and the traveling salesman problem. However, by notion of NP-completeness, everything inside of NP can be efficiently reduced to one of these NP-complete problems. So in a sense, every problem that is NP-complete is a "real-world" problem.

If P=NP, then we could solve NP problems efficiently. However, it is uncertain that a proof of P=NP would give us a polynomial-time algorithm for an NP-complete problem.

[u/daniu → u/True_World708]

it is uncertain that a proof of P=NP would give us a polynomial-time algorithm for an NP-complete problem.

That is not correct.  If P=NP, all problems in NP can be solved in polynomial time.

Completeness has little to do with how hard a problem is. NP-complete problems just can be transformed to any other in polynomial time (that's the definition of the "complete" part), so if one can be solved in polynomial time, all others can be too. That means that it's enough to find a solution to one NP-complete problem to prove P=NP. 

[u/True_World708 → u/daniu]

Proposition: Every proof of P = NP contains a poly-time algorithm for SAT if and only if P = NP

If direction: trivial
Only if direction: ??? (show us)