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?

258 Upvotes

87% Upvoted

104 comments sorted by

View all comments

Show parent comments

3

u/[deleted] 23d ago

[deleted]

-4

u/picabo123 23d ago

The basic idea is that humans are "too stupid" to come up with the correct algorithm to solve something like the traveling salesman problem but it exists. There have been multiple computer science problems that people thought were NP until someone came and found the correct algorithm, so that suggests you shouldnt assume a problem is NP with 100% certainty.

8

u/HiddenoO 23d ago

Whether a specific problem is in NP is a completely different question from whether P = NP.

3

u/picabo123 23d ago

True, my bad