The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem
Harold Connamacher, Michael S. O. Molloy · 2004
We determine the exact threshold of satisfiability for random instances of a particular NP-hard constraint satisfaction problem. The problem appears to share many of the threshold characteristics of random k-SAT for k /spl ges/ 3; for example, we prove the problem almost surely has high resolution complexity. We also prove the analogue of the (2+p)-SAT conjecture for a class of problems that includes this problem and XOR-SAT.