Today, an educated guess. The University of Houston's College of Engineering presents this series about the machines that make our civilization run, and the people whose ingenuity created them.

Mathematics is like a stack of oranges. Each new mathematical result sits atop results that came before it. And just as importantly, each new result provides a foundation for those that come later. If an important result is shown to be wrong, it's like pulling an orange from the middle of the stack. Everything on top comes crashing down.

Fortunately that doesn't happen too often. That's because mathematicians require proof — indisputable deductive proof — before they add an orange to the stack. But on rare occasion they'll do something a bit out of the ordinary: they'll conjecture a result is true even if no one's actually proved it. Then they'll continue building the mathematical orange pile while waiting for someone to come up with a proof.

Of course, there has to be good reason to take this exceptional step, and that's the case for the famous "P versus NP" conjecture. The conjecture impacts all sorts of practical problems. Internet security. Truck dispatching. Circuit board design. These are just a few of the problems that belong to a class called NP. Some of the problems in NP are known to be easy; that is, we can solve them pretty quickly. This subclass of easy problems is called P. Now, we think that many of the problems in NP are fundamentally harder than those found in the subclass P, and there's a lot of evidence pointing to that conclusion. But there's no proof. So it remains a conjecture. In the vernacular of computer science, the conjecture states, "P is not equal to NP." Proving or disproving this conjecture is considered so important, it's one of the seven millennium problems. Resolving it comes with a million dollar reward — and a place in history.

And what if the conjecture is wrong? Today's Internet security protocols rely on the difficulty of a particular problem in NP. We don't think the problem is in the subclass P, but we don't know for certain. If the conjecture is wrong, if P equals NP and the Internet security problem turns out to be easy, then all hell will break loose in the world of Internet commerce.

Less dramatic but even more consequential is what will happen to the world of problems we can solve with computers. If the conjecture's wrong, we'll wake up to find we can solve problems we thought were unimaginably difficult. And that's a good thing. But it also means countless years of human effort will cease to be of any value — a lot of oranges will come toppling down. Most experts are confident we're right. But the fact remains: we really don't know. We'll just have to wait and see what happens to our ever-growing stack of oranges. 

I'm Andy Boyd at the University of Houston, where we're interested in the way inventive minds work.

(Theme music)

---

Notes and references:

For a related episode, see OPTIMIZATION. The supplementary material to this episode contains a more detailed discussion of the classes P and NP.

Many ill-fated attempts have been made to prove P ≠ NP (and P = NP). For information on one highly visible attempt, see J. Markoff, 'Step 1: Post Elusive Proof. Step 2: Watch Fireworks.' The New York Times, August 16, 2010. See also https://www.nytimes.com/2010/08/17/science/17proof.html. Accessed September 21, 2010.

Thanks to Andrew Lienhard for suggesting this episode. 

All pictures by E. A. Boyd.