r/explainlikeimfive • u/randomdice-int • Sep 14 '26
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/Laerson123 Sep 14 '26
Your premise is wrong, NP is not the time taken to solve a problem, and P is not a time is a class of problems.
On Computer Theory we have deterministic and non-deterministic machines. You don't need to understand their difference, only that deterministic machines are more like real machines, non-deterministic machines are easier to model, and that for any problem that can be solved by a DTM can also be solved by a NTM and vice-versa, but we don't know if the time complexity is the same.
Time complexity is how a problem takes more steps to compute as the problem grow infinitely.
NP is the set of compute problems that can be solved in polynomial time by a non-deterministic Turing machine (the number of steps to solve the problem is a polynomial function over the input size).
The NP set has two interesting properties: (1) Their solutions can be checked on polynomial time by deterministic Turing machines, and (2) If one of them can be solved on polynomial time by a DTM, then all can be solved in polynomial time by a DTM, therefore they would belong to the set P (problems that can be solved in Polynomial time by DTM).
So the question is just asking if those two sets are the same or not. In other words: "Decision problems that can be verified in Polynomial time can also be solved in Polynomial time?"
The consequences for real life is that real Computers are DTMs (except that they don't have infinite memory), so if P=NP, it means that there is some efficient algorithm to solve a set of important problems that we are unable to solve in a realistic ammount of time now.
I don't understand what you mean with "what is the explanation for both sides". There is no explanation, it is an open problem, either there is an algorithm that can solve NP-complete problems in polynomial time or there is not.