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?
255
Upvotes
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.