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.
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.