Phase transitions and complexity of weighted satisfiability and other intractable parameterized problems

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