Homer Simpson Found the Solution to a $1,000,000 Problem
How the key to solving an unanswered problem in computer science might have been part of my childhood
One of my favorite DVD’s when I was a kid was The Simpsons: ‘Treehouse of Horror VI’. Like many Treehouse of Horror episodes, this one contains three segments. The third one is a favorite among nerdy Simpsons fans. The segment is called ‘Homer³’.
Desperate to avoid his sisters-in-law, Homer hides behind a bookshelf. He quickly discovers the wall behind him is penetrable and leaps in. As it turns out, the Simpson’s household contains a portal to the 3D world. In an inter-dimensional limbo, the audience is blessed with several scientific and mathematic easter eggs. These include Euler’s identity and the density parameter equation for the universe. I wrote an article about the latter from a different episode.
Today, I would like to focus on another formula seen in this episode. In one of the first shots of Homer in limbo, over his left shoulder, we see P=NP. This formula is referring to a famous unsolved problem in computer science, P vs NP.
What is P vs NP?
The main idea of this topic is to categorize problems based on the amount of time and memory a computer would need to solve them. There are so many categories of problems at this point and it would be unrealistic to cover them all, so I want to talk about the ones necessary to have a deeper understanding of the P vs NP problem.
Class P Problems
The technical definition of a class P problem, is a problem that can be solved with a deterministic machine in a polynomial time. A machine is a mathematical model that takes a set of inputs and uses a set of predefined rules to create an output. A deterministic machine is a machine which will always create the same output given the same inputs. In other words, the output is deterministic.
For a problem to be class P, the machine must be able to solve it in a polynomial time. This means the steps required to solve the most difficult version of a problem will be represented by a polynomial like, 3N or 5N² + 6N + 7, where N is the number of inputs. A problem whose solution requires 4ᴺ steps, cannot be solved in polynomial time and is therefore not a class P problem.
Let’s look at an example of a class P problem.
Currently, the first challenge on Project Euler is to find the sum of all of the multiples of 3 or 5 below 1000. This challenge only took me 6 lines of code and my computer found the solution almost instantly.
Class NP Problems
NP problems can be solved by a non-deterministic machine in a polynomial time and possible solutions to the problem can be checked with a deterministic machine in a polynomial time. Further, the number of steps required to solve this would not be in polynomial form. For example the number of steps required might look like 4ᴺ.
Let’s again refer to the Euler’s Project challenge.
It was easy to find all of the multiples of 3 or 5 under 1000 but it’s even easier to verify that a given number below 1000 is a multiple of 3 or 5. I could simply divide that number by 3 and 5. If either result is an integer, then the given number is a multiple of 3 or 5. We can conclude that this problem is both a class P and a class NP problem.
Now let’s check out a problem where it is easy to verify a solution but horrifically difficult to solve (class NP but not class P).
Imagine your company is having the big annual conference and you are put in charge of lodging. Your boss emails you a list of the 1000 attendees. There are only 500 vacant hotel rooms in town. Your task is to assign 2 employees to each room. You get started working on an algorithm to complete this task. Ding! Another email from the boss. It’s a list of employees and the employees they refuse to room with due to personal conflicts. This problem just went from trivial to daunting.
Instead imagine your boss sent you a pre-made list of room arrangements and another list of incompatible employees. All you have to do is check that there are no disallowed room arrangements. It is relatively simple to create an algorithm that can check these arrangements and can be done in a polynomial time.
A possible solution can be verified in polynomial time but the problem cannot be solved in polynomial time, so it’s an NP problem. Lots of games qualify as NP problems. For example, finding the best move in a game of chess.
It’s probably obvious by now that all class P problems are also class NP (P is a subset of NP). If a problem is easy to solve, a solution of it is easy to verify.
Other examples of NP problems
- Sudoku puzzles (larger grids)
- Chess
- The Traveling Salesman Problem
- Assembling an optimal Bitcoin block
- FreeCell Solitaire
Clay Mathematics Institute’s Millennial Problems
In 2000 the Clay Institute compiled a list of 7 unanswered questions in mathematics, each with a $1,000,000 reward for their solutions. In 2010, one of the problems was solved by Grigoriy Perelman. Now only 6 problems remain. One of these problems concerns the idea of P vs NP.
What is the problem?
The million dollar problem is this, does P = NP? Is it possible that eventually we will discover a way to solve all previously thought to be NP problems in a polynomial time? Several NP problems that were once thought to be difficult to solve have been simplified with new methods of solving and are now considered class P problems.
There are a couple factors that make this problem interesting. There is another set of problems called NP-Hard problems. These problems are hard to solve and hard to check. Fortunately, the naming convention should make this one easy to remember. A subset of NP problems and NP-Hard problems are NP-complete problems.
Any NP-Complete problem can be transformed into a different NP-Complete problem in polynomial time. That means if you solve any NP-Complete problem, you have found a means to solve them all. If you are interested in this topic I recommend reading through the presentation below by Richard Karp. The presentation itself includes logic notation, so if you’re not familiar with that, reading the abstract should suffice.
https://www.researchgate.net/publication/221580898_Reducibility_Among_Combinatorial_Problems
The Simpson’s theory for P vs NP
Most mathematicians and computer scientists believe that NP does not equal P. They think there will always be problems that in their hardest form, cannot be solved in a polynomial time.
P ≠ NP
— Most Mathematicians and Computer Scientists
Now recall from Homer’s exploration of the inter-dimensional limbo, we saw P = NP. We know from past experiences that The Simpsons, is rarely wrong about these kinds of things. If they are right, this is half of the puzzle (admittedly, proving it is the more difficult half). Is it time to shift our assumptions about ‘P vs NP’ and accept that all problems in NP will eventually prove to be P problems?
P = NP
-The Simpsons
Thank you for taking the time to read this and as always please comment if I have made a mistake anywhere or you would like to add something! Resources are linked below.
