Scientist Develops New Tool for Understanding Computational Problems

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” problems 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 problems 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 problem in theoretical computer science was formulated.

Labeled “P ≠ NP, “it asks if problems 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 Scientist 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 problem in all cases, for all integer values of N. Computer Scientist are confident, based on algorithmic complexity theory, that no such algorithm exists, thus affirming that P ≠ NP. There are many other examples of intractable problems like this.