P versus NP is an unsolved problem in computer science. I’m not going to go too in-depth on the topic, but I will cover a few aspects of P versus NP that I think are pretty exciting and a little history about it that I learned about recently. For the longest time, I thought P stood for polynomial time (it does), and NP stood for non-polynomial time (it does not). NP stands for non-deterministic polynomial time, a fancy way of saying, “If you had a non-deterministic computer, you could solve this problem in polynomial time.” So what the hell is a “non-deterministic computer”? You can think of a non-deterministic computer in a couple of ways, but before we get into that, let’s cover how a deterministic computer works.
Imagine traveling through a maze, and at each intersection, you have to choose to turn left or right. We can model this as a decision tree as below.
It takes at most seven decisions to reach the end of the tree, but only one of those paths brings us to where we want to be. On a deterministic computer, we’d have to try all paths before potentially finding the correct answer.
And it's more likely that you won’t find the correct path. As the size of the maze grows, the decision tree grows exponentially, making it even less likely that you’ll be able to find the correct path. With a deterministic computer, our only option is to “brute force” the answer and try all paths until we find the correct path.
With a non-deterministic computer, we can think of the computer as the world’s luckiest guesser.
While finding this solution might be difficult, verifying it is very simple. All we have to do is follow the path from beginning to end in seven steps to verify that the path is correct. You can also think of this non-deterministic computer as having the ability to traverse the entire tree simultaneously.
By the time it gets to step two, it’s able to travel down both paths.
In step seven, it travels down all paths simultaneously, finds one path that satisfies the requirement, and returns the correct path. It still takes seven steps to solve this problem, but it can travel the entire maze simultaneously in those seven steps.
NP problems are not just theoretical; they are all around us. If you’ve ever tackled a sudoku puzzle, you’ve encountered an NP problem. Sudoku puzzles can be challenging to solve, but their correctness can be easily verified. Sudoku puzzles belong to a particular class of NP problems known as NP-complete. This connection to everyday life underscores the relevance and importance of understanding P versus NP.
Back in 1971, Stephen Cook published a paper titled. "The complexity of theorem proving procedures" introduced the concepts that led to a paper by Richard Karp less than one year later, in 1972, called “Reducibility Among Combinatorial Problems.” that found 21 problems in the class NP-Complete that are all reducible to one another. These are the most difficult problems in NP, while all other problems are reducible to these NP-complete problems. What is interesting about this is that there is an ongoing debate on whether or not P = NP. If anyone can prove P = NP, they’d win The Millennium prize (and 1 Million dollars).
What this comes down to is that if there is a polynomial time to solve any NP-complete problem, you can solve all NP-complete problems, and any NP-complete problem can solve all NP problems in polynomial time, and this P = NP.
In complexity theory, it is typically shown in a Venn diagram like this:
If, in fact, P = NP, then that would break a lot of fundamental assumptions. One that would affect all of us is encryption technology. Two common algorithms, RSA and Diffie-Hellman, are within NP. RSA is based on the difficulty of factoring large primes, and Diffie-Hellman is based on the discrete log problem. While we don’t know if either is NP-Complete (they are most likely not; they seem to be a special type of NP problem), if we found a way to solve any NP-Complete problem in polynomial time, we could break RSA and Diffie-Hellman in polynomial time as well.
I know. It’s a lot to think about. I’ll leave you with a great video on the topic you recently shared with me. Thanks for making it this far, and I hope you have a great weekend.