Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems

We study threshold properties of random constraint satisfaction problems under a probabilistic model due to Molloy. We give a sufficient condition for the existence of a sharp threshold that leads (for boolean constraints) to a necessary and sufficient for the existence of a sharp threshold in the case where constraint templates are applied with equal probability, solving thus an open problem of Creignou and Daude.

Abstract licence: CC0

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.