Random structures, spin glasses and efficient algorithms

算法是用于解决可在计算机上实现的计算问题的系统程序。解线性方程组的高斯消去法就是一个例子。算法的运行时间是基本步骤的数量(例如，添加、修改字符串中的符号等)。该算法的执行。当然，运行时间取决于输入的大小。例如，在高斯消去法的情况下，输入的大小是写下(或输入)线性方程组所需的符号数。用m表示这个量。然后，高斯消元的运行时间被m^3限制。通常，如果对于每个可能的输入，它的运行时间被该输入的大小的多项式所限制，则算法被认为是有效的。(因此，高斯消去法是有效的。)尽管从计算的早期开始就进行了密集的研究，但仍有一大类计算问题没有有效的算法已知。根据复杂性理论，这些问题中的大多数可以归类为NP-Hard问题。布尔可满足性问题(SAT)就是一个例子。在这个问题中，输入是一个布尔公式，目标是找到满足整个公式的布尔变量的赋值(如果存在这样的令人满意的赋值)。尽管SAT问题是NP-Hard问题，但它在无数现实世界的应用中是一个子问题。事实上，SAT在计算机科学中的重要性与求解多项式方程在代数中的重要性相似。因此，大量的研究涉及到SAT的启发式算法。这一系列研究的目标是设计算法，尽可能有效地解决一般类型的SAT输入(尽管这些方法都不能有效地解决所有可能的输入)。尽管有大量的工作，但生成避开所有已知启发式算法的经验困难的问题实例仍然非常简单。要做到这一点，最简单的方法是随机绘制一个SAT公式(从合适但非常简单的概率分布中)。事实上，随机输入实例被认为是硬输入的主要例子，以至于有人建议在密码应用中利用它们的难易程度。随机SAT公式也出现在20世纪70年代以来关于算法和复杂性的开创性工作中，在那里，它们的经验硬度被认为是最令人恼火的。然而，目前还不清楚为什么这些类型的实例逃脱了所有已知的算法(更不用说如何处理这些输入了)。因此，当统计物理学家报告称一种名为调查传播(SP)的新算法在实验中有效地解决了这些硬SAT输入时，就令人惊讶了。事实上，一个天真的SP实现在几秒钟内就能解决具有一百万个变量的样本实例，而即使是以前最先进的SAT解算器也很难求解具有几百个变量的输入。SP基于自旋玻璃理论提供了一种复杂但在数学上不严格的分析。这一分析表明，为什么之前的所有算法都表现得如此糟糕。它的主要特点是将求解SAT输入的难度与解集的几何性质联系起来。尽管物理方法启发了SP算法，但它们并不能对SP的成功(或局限性)提供令人满意的解释。因此，本项目的目标是从计算机科学的角度，通过严格的数学方法，从自旋玻璃理论中研究这些新的想法。一方面，我们将对SP进行严格的分析，对其可以解决的输入类型进行分类。另一方面，我们打算从解空间几何的角度来研究算法的行为，这一角度以前没有在算法和复杂性方面进行过系统的研究。

An Algorithm is a systematic procedure for solving a computational problem that can be implemented on a computer. An example is the Gaussian elimination method for solving a system of linear equations. The running time of an algorithm is the number of elementary steps (e.g., addition, modification of a symbol in a string, etc.) that the algorithm performs. Of course, the running time depends on the size of the input. For example, in the case of Gaussian elimination the size of the input is the number of symbols needed to write down (or enter) the linear system of equations. Denote this quantity by m. Then the running time of Gaussian elimination is bounded by m^3. Generally an algorithm is considered Efficient if for every possible input its running time is bounded by a polynomial in the size of that input. (Hence, Gaussian elimination is efficient.)In spite of intensive research since the early days of computing, there is a broad class of computational problems for which no efficient algorithms are known. In terms of complexity theory, most of these problems can be classified as NP-hard . One example is the Boolean Satisfiability problem (SAT). In this problem the input is a Boolean formula, and the objective is to find an assignment to the Boolean variables that satisfies the entire formula (if such a satisfying assignment exists).Although the SAT problem is NP-hard, it occurs as a sub-problem in numberless real-world applications. In fact, SAT is of similarly eminent importance in Computer Science as solving polynomial equations is in Algebra. Therefore, an immense amount of research deals with heuristic algorithms for SAT. The goal of this line of research is to devise algorithms that can efficiently solve as general types of SAT inputs as possible (although none of these methods solves all possible inputs efficiently).Despite this bulk of work, it remains extremely simple to generate empirically hard problem instances that elude all of the known heuristic algorithms. The easiest way to do so is by drawing a SAT formula at random (from a suitable but very simple probability distribution). Indeed, random input instances were considered prime examples of hard inputs to such an extent that it was proposed to exploit their hardness in cryptographic applications. Random SAT formulas also occur prominently in the seminal work on Algorithms and Complexity from the 1970s, where their empirical hardness was reckoned most vexing . However, it remained unknown why these types of instances eluded all known algorithms (let alone how else to cope with these inputs).Therefore, it came as a surprise when statistical physicists reported that a new algorithm called Survey Propagation ( SP ) experimentally solves these hard SAT inputs efficiently. Indeed, a naive implementation of SP solves within seconds sample instances with a million of variables, while even the most advanced previous SAT solvers struggle to solve inputs with a few hundred variables. SP comes with a sophisticated but mathematically non-rigorous analysis based on ideas from spin glass theory. This analysis suggests why all prior algorithms perform so badly. Its key feature is that it links the difficulty of solving a SAT input to geometric properties of the set of solutions.Though the physics methods have inspired the SP algorithm, they do not provide a satisfactory explanation for the success (or the limitations) of SP. Therefore, the goal of this project is to study these new ideas from spin glass theory from a Computer Science perspective via mathematically rigorous methods. On the one hand, we are going to provide a rigorous analysis of SP to classify what types of inputs it can solve. On the other hand, we intend to study the behaviour of algorithms from the point of view of the solution space geometry ; this perspective has not been studied systematically in Algorithms and Complexity before.