Mathematics is often considered as an exact science and for most of us, it allows to solve all computational problems. However, they come up against certain problems that are still unsolvable, and algorithms designed to solve them have not succeeded either. Among these problems, some are less difficult and it is to them that a team of MIT has tackled and developed a new tool, the overlap gap property, to understand them.

David Gamarnik, a professor of operations research at the MIT Sloan School of Management and the Institute for Data, Systems, and Society, leads the team that has been trying to solve these “easier”, potentially impossible but less studied problems. The researchers developed a powerful tool to analyze these problems called the overlap gap property (or OGP). David Gamarnik has devoted a paper to it published in the “Proceedings of the National Academy of Sciences.”

P ≠ NP

The problem is a conjecture in mathematics, and more precisely in theoretical computer science, considered by many researchers as one of the most important. It questions whether there are problems involving large data sets for which an answer can be verified quickly, but whose solution (even if developed on the fastest available computers) would take a very long time. It is one of the seven “Millennium Prize” problems for which the Clay Institute of Mathematics is offering $1 million to the person who can solve one of them.

The conjecture P ≠ NP is still unproven, but most computer scientists believe that many well-known problems, such as the traveling salesman problem, fall into this incredibly difficult category.
William Rowan Hamilton first posed this problem as a game in 1859. The original statement was: “A commercial traveler must visit a definite number of cities once and only once and return to his point of origin. Find the order of visiting the cities that minimizes the total distance traveled by the traveler”. The solution is easy when N = 4, because there are only six possible routes to consider. But for 30 cities, there are more than 10 ³⁰ possible routes, and the numbers increase considerably from there. The greatest difficulty comes in designing an algorithm that quickly solves the problem in all cases, for all integer values of N. Computer scientists are convinced, based on algorithmic complexity theory, that no such algorithm exists, thus claiming that P ≠ NP. David Gamarnik explains:

“Such a thing is probably impossible for well understood reasons. But in real life, nature does not generate problems from an adversarial point of view. It doesn’t try to thwart you with the most difficult, hand-picked problem imaginable. In fact, people normally encounter problems in more random and less artificial circumstances, and those are the problems the OGP is supposed to solve.”

Peaks and valleys

Since the 1970s, physicists have been studying spin glasses, materials with both liquid and solid properties that exhibit unusual magnetic behavior. They seek to predict the energy states, especially the lower ones, of different spin glass structures. The situation is sometimes depicted as a “landscape” of countless mountain peaks separated by valleys, where the goal is to identify the highest peak. In this case, the highest peak actually represents the lowest energy state (although one can reverse the picture and look for the deepest hole instead). David Gamarnik states:

“This turns out to be an optimization problem similar in form to the traveling salesman’s dilemma: you have this huge collection of mountains, and the only way to find the highest one seems to be to climb each one.”

To simplify their work, the physicists considered only the height of the peaks of these mountains, David Gamarnik and his colleagues focused on their diameters: in some cases, the diameter of each peak is much smaller than the distances between individual peaks. Therefore, if one were to choose any two points in this landscape, there would be two possible solutions: either they would be very close (if they came from the same peak) or very far apart (if they came from different peaks). In other words, there would be a telling “gap” in these distances, either small or large, but nothing in between. A system in this state, proposed by David Gamarnik and his colleagues, is characterized by the OGP. David Gamarnik states:

“We found that all known algorithmically hard random problems have some version of this property – namely, that the diameter of the mountain in the schematic model is much smaller than the space between the mountains. This provides a more accurate measure of algorithmic hardness.”

Unlocking the secrets of algorithmic complexity

The OGP can provide a way to assess how hard it is to create fast algorithms to solve particular problems. David Gamarnik explains that it has already allowed them:

“to mathematically [and] rigorously exclude a large class of algorithms as potential candidates. In particular, we learned that stable algorithms – those whose output will not change much if the input changes only a little – will fail to solve this type of optimization problem.”

This negative result applies not only to conventional computers, but also to quantum computers and, more specifically, to so-called “quantum approximation optimization algorithms” (QAOA), which some researchers hoped could solve these same optimization problems.

Researchers still seem to be a long way from proving the nonexistence of fast algorithms that could solve these optimization problems in random contexts. Having such a proof would provide a definitive answer to the problem P ≠ NP. David Gamarnik concludes:

“If we could show that we cannot have an algorithm that works most of the time, that would tell us that we certainly cannot have an algorithm that works all the time.”

Translated from Une équipe du MIT s’attaque aux problèmes de calcul difficiles