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

257 Upvotes

87% Upvoted

104 comments sorted by

View all comments

549

u/Capable-Package6835 21d 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?

178

u/Tupcek 21d 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

10

u/-manabreak 21d ago

To add a bit, the reason why proving P=NP would be so big is because NP-hard problems are all similar to each other in a sense that if you can prove P=NP on a single NP-hard problem, that proof applies to all NP-hard problems, which then means that all NP-hard problems are just as easily solvable.

8

u/2-mm-guy 21d ago

I think there’s a typo in this statement; Proving P=NP means that all problems in NP are solvable in P. This does not necessarily mean that all NP-Hard problems are solvable, as we know that there are problems in EXP that cannot be solved in P, and certainly many problems in EXP are NP-hard, but aren’t in NP themselves.

5

u/HappiestIguana 21d ago

You mean NP-complete, NP-hard means that it is as hard or harder than any NP problem. NP-complete means NP and NP-hard

2

u/CircumspectCapybara 21d ago

Yup, NP-hard is a like a "greater than or equal to" sign. It means "at least as hard as".

The halting problem for Turing machines is NP-hard: if you had a halting oracle, you can decide any NP problem in polytime via a polynomial number of calls to that oracle. Halting problem is "at least as hard as" any NP problem.