Abstract
For both historical and practical reasons, the Boolean satisfiability
problem (SAT) has become one of central importance in computer science.
One type of instances arises when the clauses are chosen uniformly
randomly \textendash{} random SAT. Here, a major problem, recently
solved for sufficiently large clause length, is the satisfiability
threshold conjecture. The value of this threshold is known exactly
only for clause length $2$, and there has been a lot of research
concerning its value for arbitrary fixed clause length.
In this paper, we endeavor to study the satisfiability threshold for random industrial SAT. There is as yet no generally accepted model of industrial SAT, and we confine ourselves to one of the more common features of industrial SAT: the set of variables consists of a number of disjoint communities,
and clauses tend to consist of variables from the same community.
Our main result is that the threshold of random community-structured SAT tends
to be smaller than its counterpart for random SAT. Moreover, under
some conditions, this threshold even vanishes.
Keywords
- Constraints and SAT: Constraint Satisfaction
- Constraints and SAT: Constraints and SAT
- Constraints and SAT: SAT
