On the Phase Transitions of (k, q)–SAT

Call a sequence of k Boolean variables or their negations a k-tuple. For a set V of n Boolean variables, let T k (V) denote the set of all 2 k n k possible k-tuples on V. Randomly generate a set C of k-tuples by including every k-tuple in T k (V) independently with probability p, and let Q be a given set of q “bad” tuple assignments. An instance I = (C,Q) is called satisfiable if there exists an assignment that does not set any of the k-tuples in C to a bad tuple assignment in Q. Suppose that θ, q > 0 are fixed and e = e(n) > 0 be such that elnn/lnlnn→∞. Let k ≥ (1 + θ) log2 n and let \({p_0} = \frac{{\ln 2}}{{q{n^{k - 1}}}}\). We prove that $$\mathop {\lim }\limits_{n \to \infty } P\left[ {I is satisfiable} \right] = \left\{ {\begin{array}{*{20}c} {1,} & {p \leqslant (1 - \varepsilon )p_0 ,} \\ {0,} & {p \geqslant (1 + \varepsilon )p_0 .} \\ \end{array} } \right.$$