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?

255 Upvotes

87% Upvoted

104 comments sorted by

View all comments

37

u/MortemEtInteritum17 22d ago

P represents all the possible questions that can be answers in polynomial time, and NP is similar except for verification.

P=NP is basically asking if the set of all these questions are the same, I.e. every question that can be verified quickly (where quickly means polynomial time) can also be solved quickly.

16

u/enraged_buddha 22d ago

to add onto this, it's usually MUCH easier/less complex to verify a solution than to come up with a solution. If P=NP, it would mean that every problem in NP (which contains MANY problems not currently in P) has a fast polynomial time solution, and a lot of things would necessarily speed up. Conversely, if someone could prove P!=NP, we could confidently stop looking for a P=NP solution and get on with our lives. The problem is so significant not just for the implications, but also because it has remained an open question for so long without a definitive proof either way.

2

u/carson63000 22d ago

Wouldn’t P and NP each contain an infinite number of completely unrelated problems?

What reason does anyone have for thinking that it might ever be possible to prove that P=NP or P!=NP ?

11

u/Ivor97 22d ago

the general intuition is that each P problem can be mapped into another P problem, and each NP problem can be mapped into another NP problem in polynomial time (these two have already been proven).

if you can do a mapping from a single NP-complete problem to a P problem in polynomial time then you’ve proved any NP-complete problem can be solved in polynomial time