Some computational Problems in math and computer science can be challenging should come as no surprise. There is an entire class of issues deemed impossible to solve algorithmically. Just below this class lie slightly “easier” that are less well-understood—and maybe impossible, too.
David Gamarnik, professor of operations research at the MIT Sloan School of Management and the Institute for Data, Systems, and Society, is focusing his attention on the latter, less-studied category of Problems, which are more relevant to the everyday world because they involve randomness—an integral feature of natural systems. He and his colleagues have developed a potent tool for analyzing these called the overlap gap property.Gamarnik described the new methodology in a recent paper in the Proceedings of the National Academy of Sciences.
Fifty years ago, the most famous Problems in theoretical computer science was formulated. Labeled “P ≠ NP,” it asks if involving vast datasets exist for which an answer can be verified relatively quickly, but whose solution, even if worked out on the fastest available computers, would take an absurdly long time.The P ≠ NP conjecture is still unproven, yet most computer scientists believe that many familiar Problems like the traveling salesman fall into this impossibly hard category. The challenge in the salesman example is to find the shortest route, in terms of distance or time, through N different cities.
The task is easily managed when N=4 because there are only six possible routes to consider. There are more than 1030 possible routes, and the numbers rise dramatically from there.The greatest difficulty comes in designing an algorithm that quickly solves the Problems in all cases, for all integer values of N. Computer scientists are confident, based on algorithmic complexity theory, that no such algorithm exists, thus affirming that P ≠ NP.