What Andy is Excited About

P vs. NP: The battle of the new millenium

Mathematics is chock full of unsolved problems. Sometimes a problem can last for centuries before the next genius comes along and solves it. P vs. NP is one of those problems. However, unlike many other unsolved problems, P vs. NP has gotten special attention from educators and the media in recent years.

In this article, we’ll briefly talk about the most popular of unsolved mysteries of theoretical computer science: P vs. NP.

Algorithms: Not Just for Making Food

P vs. NP is a problem about problems. More specifically, P and NP are certain types of problems, classified by their types of solutions. The solutions to these problems are what we call algorithms. An algorithm is really just a fancy word for a well-defined procedure or protocol – like a recipe or driving directions. The field of P vs. NP is from algorithm analysis, which (among many other things) studies how fast a given algorithm runs.

Let’s do an example. Suppose you need to go through a shuffled deck of cards to find the Ace of Spades. How would you go about it? Me, I would look at each individual card of the deck until I found the Ace of Spades. How long would that take me? My algorithm could take up to 52 glances at a card until I find the Ace. Likewise, if the deck had 1,000 cards, then I might have to look at up to 1,000 cards before I found a solution. In algorithm analysis, we say that the runtime of my algorithm in terms of glances has a linear relationship to the number of cards in the deck.

Polynomial vs. Non-Polynomial Time

So can all problems be solved in linear time? Not by a long shot. For example, you cannot provide an algorithm that sorts a deck of cards in linear time every time (the optimal is n*log n for sorting, in case you’re wondering).

Furthermore, some problems take quadratic (i.e. n^2) time to solve – these are called polynomial time problems. The set of problems that can be solved in polynomial time is called P. This includes problems like sorting cards and finding the Ace of Spades in an arbitrarily large deck of cards. And there are even more difficult problems out there – the exponential problems. Exponential algorithms usually take the “try every single possibility until you find the solution” approach (a.k.a. “brute force”).

Now, mathematicians have found that there is this class of problems – called NP – where verifying that a given solution is correct can be done in polynomial time. However, nobody has ever come up with a algorithm for finding the solution in polynomial time.

One of the most famous examples is the Traveling Salesman problem. Suppose I gave you a huge roadmap of cities and roads. And then I asked you to find if there was a way to travel to each city exactly once (no skipping, no double-visits). If you find me a solution, I can check it in polynomial time by just trying out your path and checking off cities. But can you come up with an algorithm that finds the path without brute-forcing (which happens to be exponential)? Or, can you prove that no such path exists?

That’s the P vs. NP problem. Either come up with a way to solve NP problems in polynomial time (which means that P=NP), or prove that it’s impossible to come up with such an algorithm (which means P does not equal NP). Oh, and by the way, if P does equal NP, then our best encryption would be easily solvable and the whole internet would buckle. But don’t worry or anything, we’re pretty sure P is not the same as NP.

Now just like most articles here, I’ve cut out a lot of the story. A lot of progress has been made in P vs. NP, such as the development of these special NP-complete problems. Maybe that’s a topic for another day