Phys.org  January 10, 2022 The problem of optimizing over random structures emerges in many areas of science and engineering, ranging from statistical physics to machine learning and artificial intelligence. For many such structures, finding optimal solutions by means of fast algorithms is not known and often believed impossible to solve. At the same time, the formal hardness of these problems in the form of the complexity-theoretic NP-hardness is lacking. Researchers at MIT describe a new approach for algorithmic intractability in random structures, which is based on the topological disconnectivity property of the set of pairwise distances of near-optimal solutions, called […]