P vs NP, NP-Complete, and an Algorithm for Everything

This is the sixth article in a seven-part series on Algorithms and Computation, which explores how we use simple binary numbers to power our world. The first article, How Algorithms Run the World We Live In, can be found here.

When we sit down to try and solve a problem, very few of us try to figure out what kind of problem it is that we are trying to solve. In nearly every case, the answer to that question is an interesting exercise and can even help you solve the problem in some cases, but not much else. But the situation is very different with something like the Traveling Salesman Problem, which is why it is such a subject of study and research by theoretical computer scientists and mathematicians. It has everything to do with its classification as a problem.

Classifying Problems: P Vs NP

Problems that we known an efficient algorithm for that is capable of producing a solution in polynomial time are classified as P problems—P means polynomial time, in this instance. This was obviously the first subset of problems we were able to classify: of all these problems out there, at least we managed to solves these over here. Things like sorting lists, balancing trees, encrypting data are all problems that we have efficient algorithms for and so belong to the subset P.

Later, we found another subset of problems that P itself was a subset of, NP problems. The NP stands for nondeterministic polynomial time, but for our purposes, you don’t need to know too much about what that means except that its part of the foundational, Turing-era computer science that underpins every single modern computer. What you do need to know is that NP problems do not have a known algorithm that can produce a result in polynomial time.

However, if you are given a solution to an NP problem, verifying that it is correct is easy and can be done in polynomial time or less. We use this fact every time we unlock our iPhones or send messages over WhatsApp. As it turns out, NP problems are perfect for encryption; there is only one way to solve the problem that unlocks the encryption quickly, you need to have the answer ahead of time.

RELATED: 7 ESSENTIAL ALGORITHMS THAT RUN THE WORLD

Naturally, we like encryption, and we’re glad that its secure for now, but there are a lot of problems in NP that we really, really do need efficient algorithms for. Despite the best efforts of some incredibly smart people, however, there has been very little progress in solving all but a very few NP problems that we know of. This has generated one of the great unsolved math and computational problems of the past 50 years: P vs NP, also called P = NP.

What this equation asks is can any given NP problem be solved in polynomial time, thus making NP problems really P problems that just need to be properly solved, or are there NP problems for which no solution can be found in polynomial time and thus remain practically unsolvable no matter what algorithms we develop?

When looking at these two sets of problems, P vs NP, the goal is to prove one of two things: either P = NP, meaning that as a whole, NP problems as a set—including those we know of as well as any we may discover in the future—actually belong to P and can be solved in polynomial time; or P ≠ NP and that no matter what algorithm we come up with, there will be a mathematical floor on a problem’s time complexity and that floor is greater than polynomial time.

The answer to this question either way is important enough that whoever finds the answer will earn a million dollar prize from the Clay Mathematics Institute, not to mention installation into the computer science pantheon besides John Von Neumann, Alan Turing, Ada Lovelace, and other luminaries.

For many, the problem of P vs NP is mostly about the fact that there is a gap in our understanding of mathematics that needs to be filled in. Mathematicians and scientists of all disciplines abhor a vacuum of knowledge, so the solution to this problem is an important one on principle. That said, the pursuit of P = NP has immense real world implications if it is proven that, mathematically, P = NP. To understand why, we need to bring in the final two set of problems that tie it all together.

NP-Hard and NP-Complete

NP-complete is a special category of NP problems that have time complexities greater than polynomial time, are verifiable in polynomial time, and belong to a set of problems known as NP-hard. NP-hard problems are essentially those that are at least as hard as the hardest NP problem, but don’t need to be verifiable in polynomial time.

Enumerating all the possible subsets of the set of every individual atom in the universe is an NP-hard problem. We cannot prove that such a problem is unsolvable in polynomial time, but there’s no reason to believe that we’ll ever find that algorithm or even build a machine powerful enough to run it and even if someone gave us an answer, we wouldn’t even begin to know how to go about verifying it.

[see-also]

Another NP-hard problem is identifying a chess move in any given board state that is the absolute best move that you could make. In order determine this, you would have to know that every other move will lead to a worse outcome, and the only way that we know how to determine that is to follow every branching path of every move, countermove, and so on that is possible with the given board position. Once you arrive at the end result of each branch of this practically infinite decision tree, you would then take the best result and say that this was the very best move you could have made.

Leaving aside the functionally impossible of actually navigating this tree within the next couple of billion billion years, if you tell me that a particular move was truly the best possible move you could have made, there is no way for me to verify this quickly. I would have to resort to the exact same brute force permutation algorithm you just used to explore every consequence of every move. Verifying the solution would take exactly as long as it took to solve the problem.

If this sounds kind of familiar, that’s because it is. This is the same basic problem as the Traveling Salesman Problem, meaning it's essentially about optimization. As it turns out, this is one of the defining characteristics of NP-complete problems; you’re really only trying to solve one problem that has countless variations and those variations encompass the entirety of what we consider essential business, policy, or research decision making.

The Algorithm for Everything

This is why P = NP matters. We can’t know for certain, but there is every reason to believe that the answer to that question runs right through NP-complete. First, any algorithm that returns a solution to an NP-complete problem in polynomial time can be modified to solve every single NP-complete problem in polynomial time, since they are all the same problem at their core.

Not just that, but part of the definition of an NP-complete problem is every problem in NP is reducible to every NP-complete problem, which means that an algorithm that solves NP-complete in polynomial time will also solve all NP problems in polynomial time as well; in other words, solving an NP-complete problem in polynomial time proves P = NP by default and effectively solves nearly all of the hardest computational problems in the real world literally overnight.

So this essentially makes the algorithm that solves an NP-complete problem in polynomial time an algorithm for everything. This is why P = NP, this weird, opaque sounding equation, holds so much promise if it can be proven true and the only real way to do that is to solve an NP-complete problem in polynomial time. That algorithm would become an algorithm that could unlock an entirely different world in an instant. There is a lot of excitement around the possibility of quantum computing precisely because it may be our best chance at solving NP-complete in polynomial time, though whether or not it can remains to be seen.

The final article in our series on Algorithms and Computation, Quantum Algorithms and the Future of Post-Classical Computing, can be found here