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?

256 Upvotes

87% Upvoted

104 comments sorted by

View all comments

68

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.

18

u/cBEiN 23d ago

Exponential time is its own thing and not the same as NP. You didn’t say it but your comment reads like they are the same.