The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem

Harold Connamacher, Michael Molloy

We determine the exact threshold of satisfiability for random instances of a particular NP-complete constraint satisfaction problem (CSP). This is the first random CSP model for wh…