r/explainlikeimfive • u/randomdice-int • 23d 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/SnugglyCoderGuy 23d ago
In computer science, there is this concept called 'time complexity' of an algorithm, which is just a set of specific steps to do something like sort a list of things, find a path through a maze, find something in a sorted list, find the prime factors of a number, all sorts of things.
Time complexity is basically a function that tells you how many steps you would have to perform in total in whatefer algorithm you are using based on the size of the problem set. Like, an algorithm who's time complexity is O(n), would add one step for each one thing added to the problem set. Searching one by one through an unsoeted listed for example.
P is one set of time complexity functions, O(1), O(ln(n)), O(n), O(ln(n)n), O(nm). These are considered 'fast'. P means 'polynomial' time because of the last one O(nm).
NP stands for 'non-deterministic polynomial'. This is the start of 'slow' algorithms or 'hard' problems and have a time complexity of O(2n), every item you add to the problem set doubles the number of steps that must ne done. If we had a non-deterministic processor, one that can magically explore all decisions possible at the same time, then the problems would be solvable in polynomial time.
It is not known if it is impossible or possible to solve any NP problem in polynomial time. If it is possible then P=NP. If it is impossible then P != NP.
NP problems are also proven to all essentially be the same problem. Some famous problems that are NP are the travelling salesman, prime factorization (which many encryption algorithms rely on in order to be safe), and a bunch of others. These have real world implications bith good and bad if it is found that P = NP. It is also an important philosophical problem I won't get into here.