Phase Transitions and Complexity of Weighted Satisfiability and Other Intractable Parameterized Problems

Yong Gao

The study of random instances of NP complete and coNP complete problems has had much impact on our understanding of the nature of hard problems. In this work, we initiate an effort to extend this line of research to random instances of intractable parameterized problems. We propose random models for a representative intractable parameterized problem, the weighted d-CNF satisfiability, and its generalization to the constraint satisfaction problem. The exact threshold for the phase transition of the proposed models is determined. Lower bounds on the time complexity of variants of the DPLL algorithm for these parameterized problems are also established. In particularly, we show that random instances of the weighted 2-CNF satisfiability, already an intractable parameterized problem, are typically easy in both of the satisfiable and unsatisfiable regions by exploiting an interesting connection between the unsatisfiability of a weighted 2-CNF formula and the existence of a Hamiltonian-cycle-like global structure.

Subjects: 9.2 Computational Complexity; 15.2 Constraint Satisfaction

Submitted: Apr 12, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.