论文标题
硬优化问题具有软边
Hard Optimization Problems have Soft Edges
论文作者
论文摘要
从图理论中找到最大的集团是经典的属性测试。在Erdös-rényiG（n，p）随机图中找到任何最大的完整子图中的任何一个。我们使用最大集团来探索问题的结构，该函数的函数，图形大小和K所寻求的集团大小。它显示一个复杂的相边界，一个台阶的楼梯在每个阶梯上，每个2 log2 n和kmax（可以找到的集团的最大尺寸）增加了1个。其每个边界都有一个有限的宽度，这些宽度允许局部算法可以找到超出无限系统研究所定义的集团。我们探讨了传统快速局部算法的许多扩展的性能，并发现在有限N处仍然可以访问大部分“硬”空间。“隐藏的集团”问题嵌入了一个比自然出现在G（n，p）随机图中的集团大。由于这样的集团是独一无二的，我们发现一旦找到隐藏集团的证据，就可以胜过最佳信息传递或光谱算法的本地搜索。
Finding a Maximum Clique is a classic property test from graph theory; find any one of the largest complete subgraphs in an Erdös-Rényi G(N, p) random graph. We use Maximum Clique to explore the structure of the problem as a function of N, the graph size, and K, the clique size sought. It displays a complex phase boundary, a staircase of steps at each of which 2log2 N and Kmax, the maximum size of a clique that can be found, increases by 1. Each of its boundaries has a finite width, and these widths allow local algorithms to find cliques beyond the limits defined by the study of infinite systems. We explore the performance of a number of extensions of traditional fast local algorithms, and find that much of the "hard" space remains accessible at finite N. The "hidden clique" problem embeds a clique somewhat larger than those which occur naturally in a G(N, p) random graph. Since such a clique is unique, we find that local searches which stop early, once evidence for the hidden clique is found, may outperform the best message passing or spectral algorithms.
