Random structures, spin glasses and efficient algorithms

算法是一个系统的程序，用于解决可以在计算机上实现的计算问题。一个例子是求解线性方程组的高斯消去法。算法的运行时间是基本步骤的数量（例如，添加、修改字符串中的符号等）算法执行的。当然，运行时间取决于输入的大小。例如，在高斯消去法的情况下，输入的大小是写下（或输入）线性方程组所需的符号数。把这个量记为m。则高斯消去法的运行时间以m^3为界。一般来说，一个算法被认为是有效的，如果对于每一个可能的输入，它的运行时间是由该输入的大小的多项式限制的。（因此，高斯消除是有效的。尽管从计算的早期开始就进行了深入的研究，但仍有大量的计算问题没有有效的算法。根据复杂性理论，这些问题中的大多数可以归类为NP难问题。一个例子是布尔可满足性问题（SAT）。在这个问题中，输入是一个布尔公式，目标是找到一个满足整个公式的布尔变量的赋值（如果存在这样一个令人满意的赋值）。虽然SAT问题是NP难的，但它在无数的现实世界应用中作为子问题出现。事实上，SAT在计算机科学中的重要性与解决代数中的多项式方程相似。因此，大量的研究涉及启发式算法的SAT。这一系列研究的目标是设计出尽可能有效地解决一般类型的SAT输入的算法（尽管这些方法都没有有效地解决所有可能的输入）。尽管有这么多的工作，它仍然非常简单地生成经验困难的问题实例，避开了所有已知的启发式算法。最简单的方法是随机绘制SAT公式（从一个合适但非常简单的概率分布中）。事实上，随机输入实例被认为是硬输入的主要例子，以至于有人建议在密码学应用中利用它们的硬度。随机SAT公式也出现在20世纪70年代关于算法和复杂性的开创性工作中，在那里他们的经验困难被认为是最令人烦恼的。然而，为什么这些类型的实例避开了所有已知的算法（更不用说如何科普这些输入）仍然是未知的。因此，当统计物理学家报告称一种名为Survey Propagation（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.