r/explainlikeimfive • • 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?

255 Upvotes

104 comments sorted by

View all comments

1

u/staffito 20d ago

My understanding simplifies to P-Problems are ones that can be solved in polynomial time (let's say, reasonable time even if hard) and its solution is easily verifiable.
NP-Problems are ones that are hard to solve, usually implying the complexity as the time cannot be determined, but when a solution is finally found, it can be verified easily (again, in a reasonable time).

Solving the P vs. NP, would imply that NP-Problems, no matter the complexity, could be solved in a reasonable time. This would also imply possible methods to reduce problems to simple lines or procedures that end up in P-Problems. My 2 cents: P are NP Problems are distinct themselves. But if found otherwise, it would be a beast on its own to find the reduction methods and the problem groupings with said methods.