Some difficult computation problems, depicted by finding the highest peak in a "landscape" of countless mountain peaks separated by valleys, can take advantage of the Overlap Gap Property: At a high enough "altitude," any two points will be either close or far apart -- but nothing in-between. David Gamarnik has developed a new tool, the Overlap Gap Property, for understanding computational problems that appear intractable. The notion that some computational problems in math and computer science can be hard should come as no surprise. There is, in fact, an entire class of problems deemed impossible to solve algorithmically. Just below this class lie slightly "easier" problems that are less well-understood -- and may be impossible, too.
Jan-15-2022, 11:06:59 GMT