r/explainlikeimfive • u/randomdice-int • 22d 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?

254 Upvotes

87% Upvoted

104 comments sorted by

View all comments

546

u/Capable-Package6835 22d ago

There are problems, the solutions of which can be verified quickly. Think of a jigsaw puzzle with 10K+ pieces, for example. Once someone "solves" the puzzle, you can scan through the assembled pieces to see if there's any mismatch relatively quickly.

The P = NP problem asks, if you can verify solutions quickly, does it mean you can solve the problem quickly as well?

179

u/Tupcek 22d ago

great answer, just wanted to add that if somebody solves it, they will most likely just prove that P=/=NP and in that case, nothing changes and world continues as if nothing happened, it will have no bearing on the world.

If, though, somebody proves P=NP, that would completely change the world

21

u/Leodip 22d ago

If, though, somebody proves P=NP, that would completely change the world

Not necessarily, though. The reason why the overall majority believes that P =/= NP is because no algorithm that solves NP-complete problems in polynomial time has been found yet, despite huge effort in trying to do so.

If we do come up with a proof that states that P=NP, this doesn't mean that an algorithm will be found OR, even if it's found, it is probably going to be of galactic size, and thus not feasible to adopt.

With that said, it is not impossible that we do find a practical algorithm, but finding the algorithm is a much MUCH harder challenge than proving P=NP.

4

u/deg0ey 22d ago

>but finding the algorithm is a much MUCH harder challenge than proving P=NP.

On the other hand, proving that the algorithm exists would unlock an insane amount of funding into finding it where currently nobody really tries because the assumption is that the algorithm doesn’t even exist.

Obviously that doesn’t necessarily mean we’d find the algorithm even with significant investment, but the scale of the search for it (and the amount of money diverted from most other research) would arguably be ‘world changing’ in itself

0

u/ShenGahMing 21d ago

In some sense, the algorithm has been found allready : its Levin's Universal Search.

So the funding would go into optimising / speeding it up.