Structure and randomness of NP-complete problems

NP-完全问题，如可满足性(SAT)、约束满足(CSP)、规划、哈密顿循环等，有着广泛的实际应用，从硬件和软件的形式化验证到寻找邮件递送的最佳路径。在过去的十年里，NP-完全问题的求解总体上取得了令人印象深刻的进展，特别是在可满足性方面。这一进展是寻找新的、具有挑战性的实例和设计能够应对挑战的高效解算器之间长期竞争的结果。我们认为，产生新的具有挑战性的实例/模型对于提高我们解决难题的能力是不够的--还需要对新实例进行表征和分类。这确保了在求解某些实例方面取得的任何进展都可以用于(或改编)求解整个实例类。在这个方向上的第一步是调查这些实例的结构属性，并评估这些属性对实例难度的影响。主要目标是更好地理解、描述、分类和比较实例。我们打算通过研究两个NP-完全问题的实例来实现这一目标：子图同构和可满足性、它们的转换、它们的结构性质以及这些性质与实例硬度之间的关系。希望本研究能在实证和理论两方面做出贡献。虽然本文的研究工作主要集中在子图同构和可满足性方面，但其结果也可应用于其他NP-完全问题。我们相信，通过研究实例的结构及其对实例硬度的影响，可以通过识别实例的一些性质来提高我们解决组合困难问题的能力，这些性质可以用于设计更有效的求解器。

NP-complete problems, such as Satisfiability(SAT), Constraint Satisfaction(CSP), Planning, Hamiltonian Cycle etc, have many practical applications, ranging from formal verification of hardware and software to finding the best route for mail delivery. The last decade witnessed impressive progress of the solvers of NP-complete problems in general, and Satisfiability in particular. This progress was the result of a permanent competition between finding new, challenging instances and designing efficient solvers able to tackle the challenges. We believe that producing new challenging instances/models is not enough for improving our ability to solve hard problems - characterizing and classifying the new instances is also necessary. This ensures that any progress made in solving some instances can be used (or adapted) to solve an entire class of instances. The first moves in this direction are to investigate the structural properties of these instances and to assess the influence of these properties on the instances difficulty. The main goal is to better understand, characterize, classify and compare instances. We intend to pursue this goal by investigating instances of two NP-complete problems: Subgraph Isomorphism and Satisfiability, their conversions, their structural properties and the relationship between these properties and instance hardness. This research is expected to make both empirical and theoretical contributions. Although this research work focuses on Subgraph Isomorphism and Satisfiability, its results may be applied or adapted to other NP-complete problems. We believe that the investigation of the structure and its influence on instances hardness has the potential of improving our ability to solve hard combinatorial problems by identifying some properties of the instances which can be used for designing more efficient solvers.