Structure and randomness of 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.