A sharp threshold for a random constraint satisfaction problem

作者：Flaxman AD^*

来源：Discrete Mathematics, 2004, 285(1-3): 301-305.

DOI：10.1016/j.disc.2004.05.002

• random structures
• constraint satisfaction
• threshold phenomena
• phase transition

We consider random instances I of a constraint satisfaction problem generalizing k-SAT: given a set of ordered k-tuples over it 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 = Omega(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.

• 出版日期2004-8-6