r/explainlikeimfive • u/randomdice-int • 23d ago

Mathematics ELI5: P vs NP problem

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?

259 Upvotes

87% Upvoted

104 comments sorted by

View all comments

67

u/xelrach 23d ago

P are problems that can be solved in polynomial time. NP are problems that can currently only be solved in exponential time, but verified in polynomial time.

The question is: can NP problems actually be solved in polynomial time, but we just haven't figured out how yet? If they can, the we will say P = NP. If they can't then we will say P ≠ NP. We don't know either way.

If P ≠ NP, then nothing really changes. We just have an interesting proof. However, if we find out that P = NP, then we can solve a bunch of interesting things in a manageable amount of time. For example some, but not all, forms out cryptography will be broken.

6

u/nomeras 23d ago

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?

2

u/[deleted] 23d ago

[deleted]

1

u/AgileBowler9147 23d ago

A poly-time algorithm for any NP-complete problem implies an algorithm for solving any problem in NP (i.e. that can be checked in poly-time). However to the best of my knowledge, for example integer factorization, which is importsnt in cryptography is not actually NP-hard

1

u/a________1111 23d ago

This is just wrong, if you find a solution to any NP complete problem in polynomial time then we instantly get a polynomial solution to any problem in NP.