Some problems are so complex that they could take trillions of years to solve
Beyond guess and check
By Alaina O’Regan
Illustration by Dan Page
Consider a traveling salesperson who has to visit several cities scattered across the country. What route would minimize the distance that the salesperson has to travel? There is no formula, no simple algorithm, for finding the answer, and adding more cities makes the answer take exponentially longer to find.
This conundrum falls into the category of problems that, once you find the solution, are easy to check to see if you were right. However, finding the solution in the first place is virtually impossible because of the time it would take even a powerful computer to guess and check all the possibilities. In Princeton’s mathematics department, researchers tackle a range of questions about the structure of our world, delving into problems that can have profound impacts at the theoretical level as well as in practical applications such as the design of computer algorithms to solve problems efficiently. In this feature, we meet two professors who are fascinated by why some problems resist mathematical solutions and who look for ways to move beyond guess and check.
Hat guessing games
Whether the debate is about politics, popular culture or even science, it can be difficult or impossible for one person to convince another to change sides in an argument. But in mathematics, once something is proven true, it remains true forever. It ceases to be up for interpretation. This unique feature is part of what intrigues Noga Alon, a professor of mathematics and applied and computational mathematics at Princeton.
Noga Alon studies questions represented by scenarios such as children guessing at the color of each other’s hats and thieves squabbling over how to divide a stolen necklace.
Much of Alon’s work is in the crossover of mathematics and computer science, and he is interested in whether computers can solve certain problems in math efficiently. To solve a problem efficiently goes beyond simply coming up with an answer, but refers to the time and effort it takes for a computer to come up with and solve an efficient procedure, or algorithm, that avoids a systematic guess-and-check process. A proof that provides an efficient procedure for solving a problem is known as a constructive proof.
Many of the problems that Alon works on deal with quantities whose answers can be verified quickly but that, like the traveling salesperson problem, are extremely time-consuming to solve. These problems are known as NP-hard problems. [See P vs NP box.] If a computation for any NP-hard problem can be done efficiently, it would mean every NP problem could be solved using an efficient algorithm.
One problem that intrigues Alon involves the “four-color theorem,” which states that any map that can be drawn on a plane, or on the surface of a sphere, can be filled in using four colors so that no two bordering regions share the same color.
This theorem has a constructive proof, as it answers the “yes” or “no” question of whether or not four colors are always enough to fill in any planar map, and the proof that four colors always suffice provides an efficient algorithm to find the required coloring. It’s a simple concept, but this statement took well over 100 years to prove.
Alon took this theorem a step further with a proof for a related formulation of the problem with more restrictions. In this version, only the region’s edges are colored, and each edge is assigned a random list of three colors it is allowed to have.
For example, one edge may have a list that says “green, blue or yellow,” while its neighbor has a list that says “green, red or orange.” Alon used algebraic methods to show that a map can be shaded under these conditions so that no two bordering edges share the same color.
Unlike the simpler four-color problem, Alon’s proof that this can be accomplished is not a constructive proof. If we wanted to ask exactly how to color in this map, that would be difficult. Many mathematicians believe it is highly unlikely that a constructive proof could exist for this problem.
Alon applied a related algebraic approach for tackling another problem that he calls the “hat guessing game.” Imagine a room full of 100 boys and 100 girls, each lined up on opposite walls and each wearing a hat of a specified color. All of the boys can see all of the girls but cannot see each other (or themselves), and vice versa. Provided information about how many different colors of hats there are, can we ensure that at least one person will be able to correctly guess the color of their own hat based on what they see? And if so, how might this be done?
Alon discovered that both the answer and the approach change depending on the number of hat colors. If there are less than four hat colors, the problem can be solved using a simple linear guessing function. But when there are four colors or more, the problem becomes more complicated and requires nonlinear functions. This means that rather than a simple formula for the function as a whole, each person now has their own distinct, “random-looking” formula that they will use to make their guess. The solution becomes more complex as we increase the number of people and of different hat colors.
There is another set of problems that Alon has famously contributed to, called “necklace splitting.” Picture a necklace composed of rubies and diamonds, strung together in random order. The question is, how can two partners, or thieves, share this necklace evenly by making the fewest number of cuts in the necklace?
This problem becomes more difficult when there are more thieves and a larger variety of gemstones. Alon discovered that at a certain point, the problem takes a surprising turn by changing from a question of combinatorics – how many possible combinations of elements and how are they related to each other – to a question of topology, an entirely different branch of mathematics that studies continuous structures.
“The question is not that difficult, but you have to realize that it should be treated by using tools from topology,” he said. “It’s always nice to find connections between areas that appear to be totally unrelated.”
Alon pursues this work because he finds it interesting to think about. Whether or not practical applications stem from it, or whether or not he will be able to contribute to the P versus NP problem, is not the main motivation behind his research. His passion for math has led him to publish over five hundred research papers throughout his career, many of which have laid important groundwork for the research of thousands of mathematicians all over the world. His contributions to math and theoretical computer science earned him the 2022 Shaw Prize in Mathematical Sciences.
“The nice thing about being a mathematician is that you are free to pursue whatever you find interesting,” Alon said. Alon encourages his graduate students and other young researchers to choose a specialty that is interesting to them, and not base that choice on their perception of what might seem to be important.
“What is and is not important in mathematics changes all the time,” he said. “The most important thing is that you go into what appeals to you because if you are passionate, you are more likely to be successful.”
The sparsest cut
When faced with a large task, it is natural to want to break it into manageable pieces that can be tackled one at a time. For this approach to work, the problem needs to be broken up in a way that makes sense. If the individual pieces have too many connections or are too reliant on one another, solving them individually isn’t going to work.
This situation describes a problem that mathematicians and computer scientists have been working on for decades, called the “sparsest cut problem.”
Assaf Naor explores how to design computer algorithms that partition a “universe” of elements into pieces so that they have the fewest connections between them.
The goal of the sparsest cut problem is to divide a “universe” into two pieces so that they have the least total connection between them relative to their size. Each piece can then be partitioned repeatedly until they are all small enough to handle.
This “universe” could be any collection of objects with pairwise interactions, such as a network of people, a collection of molecules or a collection of websites. A universe is defined simply as a system of elements with measurements of the strength of the interactions between each pair of elements.
“Understanding the power and limitations of algorithms for the sparsest cut problem leads to questions which you can choose to approach either from the mathematics or the computer science perspective, and they’re both equally interesting,” said Assaf Naor, professor of mathematics.
Finding a foolproof algorithm – a set of steps to take to solve a problem – that will allow a computer to find the best possible partition has proven extremely difficult. So difficult, in fact, that the sparsest cut problem falls into the category of “NP-hard” problems, which consists of tasks that are thought to be impossible for a computer to solve in any reasonable amount of time. [See P vs NP box.]
For the sparsest cut problem, along with many other problems that fall under the umbrella of NP-hard, researchers are working to find algorithms that come as close as possible to the optimal solution, but do not hope to find it exactly.
“The game here is not to find the best way to partition the universe, the game is to come close to it,” Naor said. “That’s what’s called an approximation algorithm.”
The best-known approximation algorithm for this problem was proposed in the mid-1990s by Michel Goemans and Nathan Linial, the latter one of Naor’s teachers at the Hebrew University of Jerusalem.
Their method, known as the Goemans-Linial algorithm, was successful in partitioning a universe into pieces, but it was unknown how close the algorithm actually was to finding the best, or sparsest, cut.
“It’s a concrete algorithm that does partition the world into pieces but they didn’t know how well this algorithm performs,” Naor said. “They suspected, or hoped, that this algorithm would actually solve the problem, and that it would get close to the minimum up to a certain factor.”
It took 20 years, but in 2017, Naor and his colleague Robert Young of New York University were able to show precisely how well this algorithm works.
“I can cook up a universe for which I can prove that this algorithm messes up in the worst-possible way,” Naor said. “And the bad guy here is something called a Heisenberg group.”
Heisenberg groups are mathematical objects that arise in both classical mathematics and physics. When Naor and Young wanted to find out if the Goemans-Linial algorithm would successfully partition this complicated structure, it turned out that the Heisenberg group fooled the algorithm.
This result departs completely from traditional computer science, and they could have only found it from a vantage point of high level, abstract mathematics. This is partly because the Heisenberg group that works for their purpose is a mathematical object that exists in five dimensions, meaning you probably will never see one sitting on the sidewalk on your way to work.
But just because it doesn’t physically exist in our world doesn’t mean it isn’t “real,” in the sense that mathematicians and physicists can use it to deepen their understanding of mathematical theories, and to learn things about our world.
A few years later, in 2020, Naor and Young figured out how the issue that they understood in five dimensions plays out in three dimensions. They used this knowledge, which arose initially from the need to solve an algorithmic question, to solve even older open questions in pure mathematics.
Finding algorithms for the sparsest cut problem has implications for computer scientists, for example by helping to manage large data sets, among other things. For Naor, the possible application is not what drives him to pursue the research.
“The application is a huge plus. It excites me, but I would have thought about it anyway,” he said.
Many of the problems Naor thinks about have potential for real-world application, such as the sparsest cut problem, while others remain in the realm of the theoretical. Naor emphasizes, however, that these two are not necessarily mutually exclusive. “There are objects that are abstract to imagine, but oftentimes you’re using them to answer concrete questions,” Naor said.
Naor said he is happy with the progress he’s made with the sparsest cut problem, but says that there is more to understand about it, yet he has “no idea” what the next steps are.
That may sound intimidating to some, but to Naor and many mathematicians, the “not knowing” is what makes it attractive.
“Mathematical research is partly about embracing questions,” Naor said. “This feeling of being surrounded by the unknown is a positive. It doesn’t scare us, it attracts us.”
P versus NP: A million-dollar question
Computer scientists place problems into categories, called complexity classes, based on how difficult they are to solve.
Of many defined complexity classes, two of the most relevant are “P” and “NP.” There is a one million dollar prize on the line offered by the Clay Mathematics Institute to anyone who can prove, or disprove, that P and NP actually refer to the same set of questions.
P stands for polynomial time. It refers to problems that are considered “easy” for a computer to solve. The time it takes does not increase exponentially when the problem has more elements to consider.
Example: Identifying the largest number in a given list. A computer can use an algorithm to run through a list of numbers, and keep note of the largest number it has recorded so far. The more numbers on the list, the longer this problem takes, but the amount of time it takes is directly proportional to how long the list is.
NP stands for nondeterministic polynomial time. These are problems for which a proposed solution can be quickly verified by a computer, but that could take an unreasonable amount of time for a computer to solve.
Example: Finding all prime factors of a large number. A computer can use some cleverly developed methods to solve this, but even the best-known ones could take trillions of years for numbers with several thousand digits. A computer can, however, quickly verify the correctness of a proposed solution.
You must be logged in to post a comment.