A sharp threshold for a random constraint satisfaction problem

We consider random instances I of a constraint satisfaction problem generalizing k-SAT: given a set of ordered k-tuples over n literals, and a set of q “bad” clause assignments, find an assignment which does not set any of the k-tuples to a bad clause assignment. We consider the case where k=Ω(log n), and study the probability of satisfiability for a random instance I formed by including every k-tuple of literals independently with probability p. Appropriate choice of the bad clause assignments results in random instances of k-SAT and not-all-equal k-SAT. A second moment method calculation yields the sharp thresholdlimn→∞ Pr[I is satisfiable]=1if p⩽(1−ε)ln 2/qnk−1,0if p⩾(1+ε)ln 2/qnk−1.