The Golden Ticket.

Lance Fortnow wrote a piece for Communications of the Association for Computing Machinery in 2009 on the state of the P vs NP problem, one of the most important unsolved problems in both mathematics and computer science. That article led to the short (~175 page) book The Golden Ticket: P, NP, and the Search for the Impossible, which I recently read in its Kindle edition (it’s also on iBooks); Fortnow does a solid job of making an abstruse problem accessible to a wider audience, even engaging in some flights of fancy describing a world in which P equals NP … which is almost certainly not true (but we haven’t proven that yet either!).

P vs NP, which was first posed by Kurt Gödel in 1956, is one of the seven Millennium Problems posed by the Clay Mathematics Institute in 2000; solve one and you get a million bucks. One of them, proving the Poincaré Conjecture (which relates to the shape of the universe), was solved in 2010. But if you solve P vs NP affirmatively, you can probably solve the remaining five and collect a cool $6 million for your problems. You’ll find a box of materials under your desk.

Of course, this is far from an easy question to solve. P and NP are two classes of problems in computer science, and while it seems probable that they are not equivalent, no one’s been able to prove that yet. P is the set of all problems that can be quickly (in deterministic polynomial time – so, like, before the heat death of the universe) solved by an efficient algorithm; NP is the set of all problems whose solutions, once found, can be quickly verified by an efficient algorithm. For example, factoring a huge composite number is in NP: There is no known efficient algorithm to factor a large number, but once we’ve found two factors, a computer can quickly verify that the solution is correct. The “traveling salesman problem” is also in NP; it’s considered NP-complete, meaning that it is in NP and in NP-hard, the set of all problems which are at least as hard as the hardest problems in NP. We can find good solutions to many NP-hard problems using heuristics, but we do not have efficient algorithms to find the optimal solution to such a problem.

If P does in fact equal NP, then we can find efficient algorithms for all problems in NP, even those problems that are NP-complete, and Fortnow details all of these consequences, both positive and negative. One major negative consequence, and one in which Fortnow spends a significant amount of time, would be the effective death of most current systems of cryptography, including public-key cryptography and one-way hashing functions. (In fact, the existence of one-way functions as a mathematical truth is still an unsolved problem; if they exist, then P does not equal NP.) But the positive consequences are rather enormous; Fortnow gives numerous examples, the most striking one is the potential for quickly developing individualized medicines to treat cancer and other diseases where protein structure prediction is an obstacle in quickly crafting effective treatments. He also works in a baseball story, where the game has been dramatically changed across the board by the discovery that P=NP – from better scheduling to accurate ball/strike calls (but only in the minors) to the 2022 prohibition of the use of computers in the dugout. It’s Shangri-La territory, but serves to underscore the value of an affirmative proof: If we can solve NP problems in deterministic polynomial time (as opposed to nondeterministic polynomial time, where NP gets its name), our ability to tease relationships out of huge databases and find solutions to seemingly intractable logical and mathematical problems is far greater than we realized.

Of course, P probably doesn’t equal NP, because that would just be too easy. That doesn’t mean that NP-complete problems are lost causes, but that those who work in those areas – operations research, medicine, cryptography, and so on – have to use other methods to find solutions that are merely good rather than optimal. Those methods include using heuristics that simplify the problem, approximating solutions, and solving a different but related problem that’s in P. If Fortnow falls short at all in this book, it’s in devoting so much more time to the brigadoon where P=NP and less to the likely real world quandary of solving NP-complete problems in a universe where P≠NP. He also gives over a chapter to the still theoretical promise of quantum computing, including its applications to cryptography (significant) and teleportation (come on), but it seems like a digression from the core question in The Golden Ticket. We don’t know if P equals NP, but as Fortnow reiterates in the conclusion, even thinking about the question and possible approaches to proving it in either direction affect work in various fields that underpin most of our current technological infrastructure. If you’ve ever bought anything online, or even logged into web-based email, you’ve used a bit of technology that only works because, as of right now, we can’t prove that P=NP. For a very fundamental question, the P vs NP problem is scarcely known, and Fortnow does a strong job of presenting it in a way that many more readers can understand it.

If this sounds like it’s up your alley or you’ve already read it, I also suggest John Derbyshire’s Prime Obsession, about the Riemann Hypothesis, another of the Clay Millennium Institute’s six as-yet unsolved problems.