Paper Info
Title
Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
Abstract
This paper discusses a model of constraint satisfaction problems known as uniquely extendible constraint satisfaction problems. This model includes and generalizes XOR-SAT, and the model includes an NP-complete problem that appears to share many of the threshold characteristics of random SAT. In this paper we find an exact threshold in the behavior of two versions of DPLL on random instances of this problem. One version uses the unit clause heuristic, and the other uses the generalized unit clause heuristic. Specifically, for DPLL with the unit clause heuristic, we prove that there is a clause density c, smaller than the satisfiability threshold, such that for random instances with density smaller than this threshold, DPLL with unit clause will find a satisfying assignment in linear time, with uniformly positive probability. However, for random instances with density larger than this threshold, DPLL with unit clause will require exponential time, with uniformly positive probability, to find a satisfying assignment. We then find the equivalent threshold density for DPLL with the generalized unit clause heuristic. We also prove the analog of the (2+p)-SAT Conjecture for this class of problems.
Year
DOI
Venue
2012
10.1016/j.tcs.2011.11.014
Theor. Comput. Sci.
Keywords
DocType
Volume
random instance,NP-complete extension,equivalent threshold density,satisfiability threshold,satisfying assignment,positive probability,random XOR-SAT,unit clause,generalized unit clause heuristic,exact threshold,clause density,unit clause heuristic
Journal
421,
ISSN
Citations 
PageRank 
0304-3975
2
0.42
References 
Authors
50
1
Name
Order
Citations
PageRank
Harold Connamacher120.76