2021/08/01 by David Gamarnik · 1 voice · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Constraint Satisfaction and Optimization #Topological and Geometric Data Analysis #cs.CC #math.PR
paper · pdf · doi:10.1073/pnas.2108492118
arxiv published 2021/08/01 · arxiv updated 2021/08/01 · openalex publication_date 2021/10/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
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 is believed not to be possible. At the same time, the formal hardness of these problems in the form of the complexity-theoretic NP -hardness is lacking. A new approach for algorithmic intractability in random structures is described in this article, which is based on the topological disconnectivity property of the set of pairwise distances of near-optimal solutions, called the Overlap Gap Property. The article demonstrates how this property 1) emerges in most models known to exhibit an apparent algorithmic hardness; 2) is consistent with the hardness/tractability phase transition for many models analyzed to the day; and, importantly, 3) allows to mathematically rigorously rule out a large class of algorithms as potential contenders, specifically the algorithms that exhibit the input stability (insensitivity).