Does P = NP? No one really knows at this point, and you can get a million dollars if you figure it out. The first step to earning a million dollars is thus determining what the question means. In a nutshell, it asks whether any problem with a solution that can be verified quickly can also be solved quickly.
There’s a lot in there, so we need to break it down. First, what does quickly mean? In this context, quickly means that the algorithm runs in polynomial time.
But what does polynomial time mean?
Polynomial time refers to the time complexity of the algorithm, or how long it takes to find a solution. Time complexity is generally expressed using Big O notation. Polynomial time specifically means that the running time for the algorithm is upper bounded by a polynomial the size of the algorithm input:
O(n^c)
An algorithm of exponential time complexity has a runtime of:
O(c^n)
It is immediately obvious that an algorithm of exponential time complexity will grow much faster than an algorithm of polynomial time complexity, regardless of the value of the constant C. This is why an algorithm must be of polynomial time complexity to be considered quick.
Problems that can be solved by an algorithm in polynomial time are Class P problems. Problems that cannot be solved in polynomial time, but with an answer that can be verified in polynomial time, are Class NP problems.
An example of a class P problem is string matching:
Given two strings, P and T, determine whether P occurs as a contiguous substring of T.
If P= “rocket” and T= “The rocketry expert is here” the answer is yes. The algorithm can simply check each position in T to see if P occurs at that position. If we suppose that P has length U and T has length V, there are V-U+1 positions to check, and it takes no more than U steps to check each position. This makes the total time to solve the problem proportional to U(V-U+1). We can see that the time taken is highest when V is about 2U, which means u = (n/3), and the time is (n/3)(n/3), which is O(n^2) in Big O notation.
An example of a class NP problem is Integer Factorization:
Given integers n and m, is there and integer f with 1 < f < m such f divides n?
If someone gives us an answer to this problem (n, m, and 1 < f < m, with the claim that f is a factor of n), we can easily check the result in polynomial time by performing the division n/f. While algorithms to solve this problem do exist, they all run in exponential time.
Given this background, we can understand what the question P = NP? Is asking. It is asking whether, since a solution to problems like Integer Factorization can be verified so quickly, it is possible to find a solution in a comparable amount of time?
Why is this important?
If it turns out that P = NP is true, then there is a faster solution for all class NP problems, and we just haven’t found it yet. If !P = NP, then at least some subset of NP problems are not possible to solve in polynomial time. This essentially tells us which problems are easy for computers to solve, and which are not (note that a problem being class P does not necessarily mean that it is efficient for current computers to solve, only that a theoretical computer is capable of efficiently solving it). It is currently assumed that P != NP, so ultimately a proof showing this to be the case would only confirm what most already believe to be true. This conclusion would change little, although it would affirm most current cryptography techniques, which depend on our inability to efficiently factor large numbers. It would also show that the current approach to NP problems, which is to find workarounds to convert them to P problems, is our best path forward. The exciting, if unlikely, possibility is that P = NP. Public-key cryptography would become impossible. Everything would be ultra optimized, from transportation to computation. Artificial intelligence would make massive leaps. This conclusion would radically alter our whole world.
Top comments (0)