We consider random instances I of a constraint satisfaction problem generalizing k-SAT: given n boolean variables, m ordered k-tuples of literals, and 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 generate instance I 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 notall-equal k-SAT. For constant q, a second moment method calculation yields the sharp threshold
['Abraham D. Flaxman']
A sharp threshold for a random constraint satisfaction problem