Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems

2005/03/29 by Gabriel Istrate, Istrate, Gabriel
Computer Science · #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.CC #cs.DM

paper · pdf · doi:10.48550/arxiv.cs/0503083

A revised version of this paper will appear in Discrete Applied Mathematics

arxiv created 2005/03/29 · arxiv updated 2009/12/01

Abstract

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.

Related

• Sharp Thresholds for Constraint Satisfaction Problem and Graph Homomorphisms
• General Bounds on Satisfiability Thresholds for Random CSPs via Fourier Analysis
• The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem
• Reconstruction and Clustering in Random Constraint Satisfaction Problems
• Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems