Structure and randomness of NP-complete problems

NP完全问题的结构和随机性

• 批准号: 327477-2006
• 负责人: Anton, CalinDoru
• 金额: $ 0.73万
• 依托单位: University of Alberta
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=363602
• 关键词: Structure; randomness; NP; complete; problems

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.

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