SAT 2004 START ConferenceManager    


A Random Constraint Satisfaction Problem That Seems Hard for DPLL

Harold Connamacher

Presented at The Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT 2004), Vancouver, BC, Canada, 10-13 May 2004


Abstract

This paper discusses an NP-complete constraint satisfaction problem which appears to share many of the threshold characteristics of SAT but is similar to XORSAT and so is easier to analyze. For example, the exact satisfiability threshold for this problem is known and random instances drawn from the satisfiability threshold have high resolution complexity. In this paper, we prove the problem appears hard for DPLL. Specifically, if we pick a problem instance at random with constraint density higher than some given threshold but below the satisfiability threshold, a DPLL backtracking algorithm using the unit clause heuristic will, with positive probability, take exponential time to find a satisfying assignment.


  
START Conference Manager (V2.47.2)
Maintainer: rrgerber@softconf.com