www.scientificamerican.com
OpinionJanuary 6, 20257 min readThe Math Mystery That Connects Sudoku, Flight Schedules and Protein FoldingThousands of notoriously difficult problems in computer science are actually the same problem in disguiseBy Jack Murtagh edited by Jeanna BrynerWith 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. Natalia Barliaeva/Getty ImagesComputer science seemingly rides a curve of unstoppable progress. Mere decades took us from vacuum tubes to microchips, dial-up to high-speed Internet and Office Assistant Clippy to ChatGPT. Yet thousands of everyday problems across science and industry remain just as unsolvable for todays fleet of AI-powered supercomputers as ever.These notoriously hard NP-complete problems promise 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: those thousand-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.Finding fast algorithms for these NP-complete problems (or proving that no such algorithms exist) would resolve the P versus NP question, which is the most important mystery in computer science. P refers to the set of computational problems that computers can solve efficiently. NP, meanwhile, stands for the problemswhose solutions can be verified efficiently. But those problems cant necessarily be solved quickly. NP includes everything in P (because finding a solution is a perfectly good way to verify it) but also harder problems for which we dont know efficient methods for finding solutions. We can only verify them once they are solved. The P versus NP question asks whether this apparent asymmetry between finding a solution and verifying one is real or illusory. Maybe P = NP, and they refer to the same set of problems. In other words, maybe the NP problems that we dont know how to solve efficiently only appear hard relative to P problems because we have yet to find the right insights.On supporting science journalismIf you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.For example, is there an algorithm (a recipe of simple instructions) that, given any large list of cities, the flights connecting them and a budget, would efficiently decide whether you can visit them all while respecting the budget? We dont know. We do know an inefficient algorithm: check every possible sequence of flights that visits all of the cities, add up the cost of each, and compare the totals with the budget. But as the number of cities on the list grows, the number of routes to check explodes exponentially, quickly growing infeasible even for the fastest computers. There may or may not be some clever shortcut that circumvents this exhaustive search, but computer scientists have yet to find it. Given a solution, howeverin this case, a proposed list of flightsone could verify in a reasonable amount of time whether a route hits every city and stays under budget. If P equals NP, it implies that the flight scenario (an example of what is called the traveling salesperson problem) has a speedy solution. We just dont know it yet.Many natural computational problems join the traveling salesperson problem in the NP set. This includes challenges from logistics (such as packing boxes into trucks), social networks (finding cliques of mutual friends), biology (predicting how proteins will fold), and games such as Sudoku, Pokmon and Candy Crush. We can even cast math itself as an NP problem because its proofs can be verified efficiently. It may seem strange to classify these as hard problems when people pack boxes into trucks and solve Sudokus every day. But we consider an algorithm to have solved a problem efficiently only if it solves every instance efficiently, including very large ones. Of course, a computer can solve a 9x9 Sudoku faster than a million x million Sudoku, so the rigorous definition of efficient appeals to how the time required to solve a problem scales with the size of the input.The P versus NP question concerns a variety of computational problems and how they relate to one another, so it may seem like a resolution would require investigating each of those problems individually. Say you were to discover an efficient algorithm for the traveling salesperson problem. This would be a heroic breakthrough, but would it tell you anything about your ability to solve huge Sudokus or any other challenging NP problem? Amazingly, your algorithm for that single problem would fully resolve P versus NP. In 1972 computer scientist Richard Karp published a seminal paper demonstrating that 21 classic NP problems have a remarkable property: an efficient algorithm for solving any one of them could be used not only to solve the other 20 but to solve every problem in NP. He called these 21 problems NP-complete. In the intervening years, that list has grown as researchers discovered many other NP problems share this magic property (including the traveling salesperson one).We can view NP-completeness with optimism or pessimism. On the optimistic hand, a fortress of monstrously difficult problems standing between us and untold technological promise now looks more like a house of cards. Yank one into the realm of feasibility and the whole NP edifice collapses, and a scientific revolution rises from the rubble, filled with effortlessly efficient travel, rapid drug discovery via protein folding and a new age of mathematics. On the pessimistic hand, NP-completeness suggests that these problems do not have efficient algorithms; if all it takes to prove otherwise amounts to conquering a single problem, then why hasnt anybody succeeded yet? Most experts lean toward the latter interpretation and suspect that NP-complete problems dont have fast algorithms.Whether viewed glass half full or half empty, the concept of complete problems changed the way researchers view computation. Karp showed that he could use an algorithm for one NP-complete problem to solve another by first demonstrating that you can translate seemingly unrelated problems into each others language using a process called a reduction. This works by showing how to take any instance of one problem (such as one that involves a list of cities, flights between them and a budget) and converting it into another problem (such as a large Sudoku puzzle) in such a way that the Sudoku only has a valid solution if its possible to visit all of the cities within the budget (and doesnt have a valid solution otherwise). That way, if you discovered an efficient algorithm for Sudoku, then you could use it to also solve the traveling salesperson problem by converting instances of the latter into Sudoku puzzles. (Check out the bottom of this story for a cool example of a reduction in full detail.)This ability to encode one problem using the language of another is not just a quirk of this example but also a feature of computation itself. A web of reductions unites all NP-complete problems. Solve any one of them, and you can solve any other NP problem. The implications boggle the mind. Remember we can frame proving mathematical theorems as an NP-complete problem. Pick any famous unsolved math question. The theory of NP-completeness then tells us that there exists some level of Candy Crush that perfectly encodes your math question. If a certain score is achievable in a certain number of moves on that level of Candy Crush, then your math problem has a proof of a certain length; otherwise it doesnt. NP-completeness also assures us that certain advances in protein folding (or box packing or Sudoku solving) would destroy the digital economy. Thats because the encryption that protects our sensitive data works by vaulting them behind computational problems believed to be intractable. (Its worth noting that although solving an NP-complete problem would allow you to break encryption, the reverse isnt true; the intractable problems underlying most encryption schemes arent quite NP-complete themselves.)With all this riding on NP-complete problems, a million bucks might look like a bargain for their solution. And it might offer a bit of added motivation the next time you struggle to schedule your vacation trip or crack a Sudoku puzzle.How Does Reduction Work?For anyone who wants a deeper dive into how reduction works, lets reduce another type of NP-complete problem, the map three-coloring problem, to the clique problem. The map three-coloring problem asks: Given a map, can you assign one of three colors to each region so that no neighboring regions repeat a color? The clique problem instead asks: Given a social network, does it contain a group of a desired number of people who are all mutual friends? Both problems are NP-complete, meaning we dont know any efficient algorithm for either of them. On the surface, they have little in common. But well show that given a map, we can transform it into a social network in such a way that the answer to the social network problem will give us the answer to the map problem.Picture a U.S. map. To build a social network out of it, well designate three people for every state, one for each of three colors: blue, green and red. Well then make two people friends unless:They represent the same state. (The green Wisconsin representative will not be friends with the blue Wisconsin one.)They have the same color and represent neighboring states. (North Dakota and South Dakota share a border, so their red representatives will not be friends, but North Dakota and Florida dont, so their red representatives will be friends.)I claim that this social network of 150 people will contain a clique of 50 mutual friends only if the U.S. map has a valid three-coloring. If we found 50 mutual friends in the network, they must all represent different states because, by design, we didnt make people friends when they represented the same state. Furthermore, the coloring that corresponds to the clique would never assign neighboring states the same colorwe explicitly forbade such links in the network. So a clique of 50 people would correspond to a valid three-coloring. Likewise, if no 50-clique exists in the network, then no three-coloring exists for the map.We just reduced the map three-coloring problem to the clique problem. This means if somebody discovered a fast algorithm for the clique problem, then they could use it to solve any instance of the map three-coloring problem. Critically, the first steptransforming the map into a networkis fast. Creating the people in the network and the appropriate friendship relations does not require any exhaustive search or other infeasible computational overhead. Reductions show that even if our problems feel one of a kind, they may be more universal than they appear.This is an opinion and analysis article, and the views expressed by the author or authors are not necessarily those of Scientific American.
