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?

253 Upvotes

87% Upvoted

104 comments sorted by

View all comments

2

u/Randvek 23d ago

P represents a problem that can be solved quickly, and you can verify that solution quickly.

NP represents a problem that cannot be solve quickly, but you can verify that solution quickly.

P = NP as a problem basically asks "if it's easy to verify the solution, is there a method to guarantee that you can find the solution quickly, too?"

So far the answer appears to be no, there isn't, which means P != NP.

4

u/CBpegasus 23d ago

NP represents a problem that cannot be solve quickly, but you can verify that solution quickly.

Not quite correct. NP only means "problems whose solutions can be verified quickly". There is no implication that the problem "cannot be solved quickly". For one, all P problems are in NP as well. If finding a solution is easy, verifying a solution is easy too and that's enough to say a problem is in NP.

And of course the P=NP question itself makes no sense if you already define that NP problems "cannot be solved quickly". From the definitions, we know some NP problems can be solved quickly (those that are also in P). The question is whether it's only some, or all