Is All Math Solvable?

Thousands of notoriously difficult problems in computer science are actually the same problem in disguise

- BY JACK MURTAGH

With NP-complete problems, you could discover a fast algorithm to solve Sudoku puzzles that could also break the encryption schemes that protect our digital economy.

COMPUTER SCIENCE SEEMINGLY RIDES A CURVE of unstoppable progress. Mere decades took us from vacuum tubes to microchips, from dial-up to high-speed Internet, and from Office Assistant Clippy to ChatGPT. Yet thousands of everyday problems across science and industry remain just as unsolvable as ever for today’s fleet of supercomputers powered by artificial intelligence.

People working on these notoriously hard “NP-complete” problems could win a million-dollar prize, awarded by the nonprofit Clay Mathematics Institute, for either finding their fast solution or proving that none exists. An amazing insight from the 1970s makes this challenge even more tantalizing: these 1,000-plus problems are, in a deep sense, one and the same. If you solve one, you solve them all. This concept, now fundamental in the field of theoretical computer science, shows that certain groups of computational problems form a unified web. Discover a fast algorithm that solves Sudoku puzzles of any size, and you can now break the encryption schemes that protect our digital economy. Reveal a shortcut for scheduling a flight tour within a budget, and you can use it to solve nearly any famous open math problem.