Structure and randomness of NP-complete problems

np完全问题，如可满足性（SAT）、约束满足（CSP）、规划（Planning）、哈密顿循环（hamilton Cycle）等，有许多实际应用，从硬件和软件的正式验证到寻找邮件投递的最佳路线。在过去的十年中，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.