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 possible. At the same time the formal hardness of these problems in form of say complexity-theoretic $NP$-hardness is lacking. In this introductory article a new approach for algorithmic intractability in random structures is described, which is based on the topological disconnectivity property of the set of pair-wise distances of near optimal solutions, called the Overlap Gap Property. The article demonstrates how this property a) emerges in most models known to exhibit an apparent algorithmic hardness b) is consistent with the hardness/tractability phase transition for many models analyzed to the day, and importantly c) allows to mathematically rigorously rule out large classes of algorithms as potential contenders, in particular the algorithms exhibiting the input stability (insensitivity).
翻译:在科学和工程的许多领域,从统计物理到机器学习和人工智能,都出现了优化随机结构的问题。对于许多这类结构来说,通过快速算法找到最佳解决办法的问题并不为人所知,而且往往被认为不可能。与此同时,这些问题的形式硬性也缺乏,表现为复杂理论—理论$NP$-硬性。在引言文章中描述了随机结构中算法不易性的新办法,其依据是一套近于最佳解决办法的双向距离(称为“重叠差距财产”)的地形脱节性特性。文章展示了这种属性(a)如何出现在大多数已知的模型中,以显露出明显的算法硬性(b) 与许多分析到今天的模型的难度/可耐性阶段过渡相一致,而且重要的是(c) 允许以数学方式严格地排除作为潜在竞争者的大量算法,特别是展示投入稳定性(不敏感)的算法。