Let’s take a road trip. We’re going to visit all the capitals of all the 48 contiguous states, starting from Denver.
Now, since we’re taking vacation days to do this, we don’t want to visit any capital more than once, and we want to do this in the least time, or in the shortest distance traveled, which is pretty much the same thing.
Starting from Denver, if we only want to visit one other state capital, planning the trip is easy. Denver to Cheyenne. Boom. Two capitals is easy — you can either go Denver to Cheyenne to Topeka, or Denver to Topeka to Cheyenne. Add in Santa Fe, well, there are several routes. Ignoring, for the sake of keeping my readers awake, some details, basically as we expand the number of cities, we have to explore every possible ordering of the cities. So if we stay in Denver, visiting exactly one capital, we have exactly one route. Visit one other city, we have two choices of trip plan — Denver Cheyenne Denver, or Cheyenne Denver Cheyenne. Visit two other cities — so three cities total — and there are six choices. (Remember this includes trips where someone wants to start and end in Santa Fe or, Gods forbid, Topeka.) So, no other cities, you have 1 choice. One other city, you still only have 2 choices. Two other cities, you have six route choices.
Three other cities? Well, you can use all the routes for two other cities, and go to the new city from each of them. So you multiply the number of routes you’ve already got by the total number of cities. In other words, if we have n cities, we want n × n-1×n-2 … 1.
Many of you already recognize this as n! — “n factorial” — which is an important idea in a lot of different areas of math.
For our purposes right now, what’s important about factorial is that it grows really fast. 5! is 120, 6! is 720, 7! is 5040 — and we need routes among 48 capital cities. 48! is
…which, in computer science, is called “a lot”. Call it 12 novemdecillion, because, well, that’s roughly what it is. I’ll leave it as an exercise for the interested reader to figure out what the number is if you want to add visiting Washington DC to the tour.
This problem, how to visit many locations in the shortest time, never visiting any location more than once, is called the traveling salesman problem — “TSP” — and it turns out to be at the heart of perhaps the most significant unsolved question in Computer science.
You see, there’s no known way to solve TSP except by enumerating every single one of the possible routes and computing how long it is. We say that an efficient program to compute some value is computable in polynomial time — which just means the run time is proportional to n to some fixed power, like n3. A problem like TSP takes exponential time — the best known algorithms take time proportional to some expression like 2n. An exponential grows much faster than a polynomial; eventually as n gets large, 2n will exceed nk for any exponent k.
But now let’s go all science-fictional. Our traveling salesman is an intelligent amoeba from Arcturus. He(?) starts at a first city, and follows Yogi Berra’s advice: when he comes to a fork in the road he takes it. Since intelligent amoebas from Arcturus reproduce by fission, every time he has a choice of routes to take, he splits himself into enough copies to take every next trip available, and copies down how long it takes.
Eventually, they have together covered all the possible routes, and they can quickly determine which one was shortest by sorting the list in order of length, a process which is efficient, does take “polynomial time”. Although not necessarily a short time, we’re still sorting 12 novemdecillion routes.
Novemdecillion is not a word you get to use every day.
Now for some terminology. In computer science, we call the collection of all problems that can be solved by a conventional computer in polynomial time P. For polynomial.
Our amoebic horde — which is now being attacked by Steve McQueen and the US Air Force, because it has in the process had to eat a prodigious number of people, animals etc to sustain this rapid growth — is a model of an unconventional computer, called a nondeterministic machine. “Nondeterministic” because it doesn’t have to make a decision and determine a particular route — it can take them all. A hypothetical non-deterministic computer, like our hypothetical amoebas, can solve a problem by exploring all the possible choices simultaneously. So our non-deterministic amoeba “machine” solves the TSP for n cities in n steps, which is a polynomial. We say that the set of problems that can be solved in polynomial time by a nondeterministic machine NP. For, you guessed it, nondeterministic polynomial.
Now, here’s where it gets wild. We don’t know of an algorithm that can solve TSP in polynomial time, so we can’t say that TSP is in P; we just saw that TSP is in NP. In 1971, Stephen Cook proved that if you can solve any problem in NP in polynomial time with a conventional deterministic computer, you can solve all of them in polynomial time — because you can write a deterministic program that will transform one of these problems to any other in polynomial time. (If you multiply two polynomials, you still get a polynomial.) So every one of these problems is in some basic sense “as hard as” any other, and we call these problems NP-hard. Add in some technicalities and we speak of NP-complete, which for our purposes is essentially the same thing. A problem is NP-hard if it’s at least as hard as an NP-complete problem.
There are a lot of interesting problems that are NP-hard, but the really interesting thing is that if we ever solve any of them in polynomial time, we solve all of them in polynomial time. So if we ever solve any one of these problems in polynomial time, we know the set P is exactly the same as the set NP. This question, is P equal to NP, is one of the major unsolved problems in computer science. Of course, it would be only academically interesting if we could just build a non-deterministic computer. But of course we can’t.
Or can we?
We may not have a supply of ameboid Arcturan salesorganisms, but we had someone possibly even a little more interesting in Richard Feynmann. (In grad school, I had a friend who got an internship at Thinking Machines Inc., and had Dick Feynmann and Marvin Minsky as her officemates. I’ve never been so jealous in my life.) Feynmann observed that you could exploit some qualities of quantum mechanics to hypothetically build a quantum computer. Of course, one of the peculiarities of physics at the quantum level is that it is, in a very basic and essential way, nondeterministic. I’ll leave explaining quantum computing for another time, but basically a quantum computer stores information in qubit, quantum bits, that can exist in many states at one time.
There are many problems that seem to be as hard or harder than problems in NP that a quantum computer could solve much more quickly. One of those problems is finding prime factors of a large number.
The best known encryptions all depend, for their strength, on the fact that you can find a large prime number quickly, but you can’t decompose a large number into primes quickly.
It turns out that a quantum computer can solve NP-complete problems more quickly than any deterministic computer, and can factor a large prime in polynomial time — that is to say, “efficiently” in computer science terms. An effective quantum computer could break many of the strongest encryptions we know, and do so quickly and efficiently.
A few weeks ago, there were several news stories out that the NSA is researching how to build a “cryptographically useful” quantum computer. A quantum computer isn’t restricted in the ways a deterministic computer is, and could crack uncrackable codes, because, as Yogi Berra said, when it comes to a fork in the road, it takes it.