A sharp threshold for a random constraint satisfaction problem

@article{citeulike:1290894, abstract = {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=[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. A second moment method calculation yields the sharp threshold}, author = {Flaxman, Abraham D.}, citeulike-article-id = {1290894}, journal = {Discrete Mathematics}, keywords = {csp, random, structures}, month = {August}, number = {1-3}, pages = {301--305}, posted-at = {2007-05-11 23:15:25}, priority = {0}, title = {A sharp threshold for a random constraint satisfaction problem}, url = {http://www.sciencedirect.com/science/article/B6V00-4CNJBY8-2/2/cd7b09183edabea28d932b1238cc0587}, volume = {285}, year = {2004} }

TY - JOUR ID - citeulike:1290894 L3 - citeulike-article-id:1290894 N2 - 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=[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. A second moment method calculation yields the sharp threshold IS - 1-3 JF - Discrete Mathematics EP - 305 TI - A sharp threshold for a random constraint satisfaction problem VL - 285 SP - 301 KW - csp KW - random KW - structures AU - Flaxman, Abraham PY - 2004/08/06/ UR - http://www.sciencedirect.com/science/article/B6V00-4CNJBY8-2/2/cd7b09183edabea28d932b1238cc0587 ER -