The ‘holy grail’ of unsolved mathematical problems is often considered to be P versus NP. The legendary equation holds the answers to many of life’s biggest problems, greatest mysteries, and the cure to the world’s most dangerous diseases. Finding the answer to the problem could mean solving cancer, unlocking ‘superhuman’ capabilities in people, beating the stock market, and cracking any form of encryption. And that’s only the start of the possibilities. The answer to P vs NP could alter our future more than any other discovery in history.
The problem was first mentioned in 1956 in a letter from Kurt Gödel to John von Neumann. In the letter, Gödel asked Neumann if it was possible for a seemingly ‘noncomputable’ answer to be answered in a shorter way. Two decades later, this question resurfaced when computer scientists in the 70’s began to program computers to solve many of the worlds problems. Usually, these scientists would come up with an incredibly slow solution to a problem, but over the years these scientists would refine the solution and make the solution much faster. However, this only seemed to happen for some problems the scientists encountered. Other problems didn’t seem to have a fast solution.
In an attempt to figure out why this happened, the scientists categorized the problems into ‘fast’, ‘slow’, and ‘no freaking idea.’
The fast problems were problems like multiplication, and list sorting. The slow problems were problems like playing a perfect game of chess, or finding other perfect strategies to board games. The ‘no freaking idea’ problems were problems like the Traveling Salesman problem (defined as: Given a list of cities what is the shortest possible route that a traveling salesman can visit each city exactly once and return to the origin city?), protein structure prediction, and primes.
These scientists were content with the fast column and slow column, but were pretty pissed that they couldn’t figure out the ‘no freaking idea’ column. So they kept trying to solve the ‘no freaking idea’ problems. That was where P and NP came in.
In a disgustingly oversimplification of the problem, P vs. NP basically means this: P is the class of problems that include every problem that can be solved in a reasonable amount of time such as multiplication, or sorting through a list. Enveloping this p class, we have another class called NP. NP is all the problems where if you are given a correct solution, you can at least check this solution in a (fairly) short amount of time. NP was super frustrating to these scientists, because it turned out that this class contained many important problems, like protein folding, vehicle routing, finding primes, circuit design, and the efficiency of the stock market.
These scientists kept trying to solve many of the NP problems. Sometimes, they would get really lucky and find that a certain NP problem really belonged in the ‘P’ class and then all of a sudden it would be easy and fast to solve. For instance, the problem of prime numbers – scientists originally thought determining prime numbers were an NP problem, until it was discovered that it was in fact only a P problem.
But there is more. The scientists in the 70’s also found that some of these NP problems could actually be converted into other NP problems by using simple logic. An example of this is the Traveling Salesman Problem can actually be converted into the protein structure prediction problem. This intrigued many scientists and prompted them to explore even further. They found that other problems, like the Bandwidth problem (in computer servers) could be converted to the protein structure prediction problem, along with many other problems. These problems that could be converted into other problems were called NP-Complete problems.
This discovery was a really big deal.
It meant that if scientists managed to figure out a fast way to solve the Traveling Salesman Problem, it could be converted to solve the protein structure prediction as well. Ultimately, we could use this fast algorithm (that solved Traveling Salesman Problem) to then solve the Bandwidth Problem and all the other NP-complete problems. This means that all of the NP problems would turn into P problems.
The important thing to remember is that if P does in fact equal NP, that would mean that there has to be a fast algorithm to solve the Traveling Salesman Problem and therefore there has to be a fast algorithm to solve all of the NP-complete problems.
NP-complete is so exciting because of the way it affects us day-to-day. For example, many NP-complete problems are embedded in popular video games, like Super Mario Brothers, Sudoku, Battleship, mastermind and Tetris.
This means that if you found an efficient and fast way to play Battleship, you would end up solving cancer.
That might have all been a little confusing / a lot to take in at once. So here’s an example that I found from user jargru on Reddit. I think this explains the problem pretty well:
Some problems are easy to solve. For example, say I want to know which movie won the Oscar for Best Picture last year. Pretty easy to answer, right? Let’s call these problems P. Other problems are hard to solve. However, if given a solution, it’s easy to verify whether or not that solution is correct. For example, say I asked you to direct a movie that will win Best Picture. Pretty hard, right? But let’s say you do it. You come to me and say “I directed this year’s Academy Award winner for Best Picture.” It’s easy for me to verify whether or not you did. Hard to solve. Easy to check. Let’s call these problems NP. If P=NP then it’d be just as easy to direct the next Oscar winner for Best Picture as it is to say that Spotlight won Best Picture last year. This obviously takes some liberties, but gets at the basic idea
What are the chances that P really does = NP?
Well, it depends who you ask. If you ask a computer scientist, most of the time they are going to say that P does not equal NP. Their reasons for claiming this are as follows:
- If P = NP it would mean that thousands of NP-complete problems belong in P. Since these problems are different, logically computer scientists claim that it wouldn’t make sense to have one solution to all of these problems.
- P = NP would end modern cryptography, which has assumptions that P does not = NP.
- P = NP seems too good to be true. Many computer scientists claim that it would end modern creativity.
- P = NP would go against several known results for popular theories, such as recursion theory, set theory, finite automata, and pushdown automata.
While this sounds depressing for all those rooting for P = NP (like me), have no worry! There is another side of the research spectrum and it contains brains that are just as smart if not smarter than the computer science side.
This side of the spectrum is home to Financial Analysts.
Now, I am sure that everyone reading this is at least somewhat familiar with the stock market and has most likely seen a stock market graph, but if you haven’t seen one, here’s a comic I drew:
Stock prices go up and down and it is represented in the peaks and troughs of the graph above. The reason the stock market is so frustrating is that it seems impossible to predict when a stock will rise or fall. For instance, if you sell right at the stocks peak and then it falls, you made money! But if you sell at its trough and bought at a higher price, you lost money. It seems impossible to determine what the price will do in the future when the only reference’s you have are in the past. But if I wanted to see how the stock did yesterday, it would be easy to do that. This is like NP – hard to solve, easy to check.
Most Financial Analysts believe that the Stock Market is at least weakly efficient, meaning that past prices do not predict future prices, but that if someone has insider information or some other kind of trading information, they can predict stock prices.
That is where it gets super interesting. If the stock market is in fact weakly efficient, that would mean that P = NP.
The problems of market efficiency and P = NP are actually surprisingly similar. P = NP is a mathematical question in nature, thus the answer is bound to be mathematical in nature. The question of whether or not the market is efficient is empirical in nature, meaning that the answer will be empirical – you can see the answer in the stock market and we can experiment to prove that it is true. If P = NP, the stock market is efficient, and if P does not = NP, the stock market is inefficient. Computer scientists claim that P does not = NP. Financial Analysts claim that markets are weakly efficient.
Both cannot be right.
So what do you think?