where the fourth equation in (4.18) is due to the fact that for any positive integer n and q such that q < ~, we have n 1 e-q 2 /2 n < n 2 < n 9 . It follows that  lim E{A t } = ∞ if

$$2(3+{\sqrt{5}})r\,>\,1.$$
$$(4\,,1\,9)$$

Solving the inequality (4.19) gives us α > 0.837, that is, z = 2 + α > 2.837. This proves Theorem 4.2.

□
Based on the Chebychev's inequality, to prove that N ( n, 2, z ) contains t-3-modules with probability 1, we need to show that the variance of A t , the number of contained t-3-modules, is o( E { A t }). For this purpose, we follow Franco and Gelder's approach (Lemma 4.1, Franco & Gelder, 1998) to apply the second moment method (Alon & Spencer, 1992): Lemma 4.4. (Alon & Spencer, 1992, Ch. 4.3 Cor 3.5) Given a random structure(e.g., a random CNF formula), let W  be the set of substructures under consideration, A(w) be the set of substructures sharing some clauses with w ∈ W .  Let I w = 1 when w is in the random structure and 0 otherwise. If
(1) elements of W are symmetric;
(2) µ = E { ∑ I w } → ∞ ; and L
Pr(w | w) = o(p),  for each w ∈ W,
(3)
WEA (W)
then as n → ∞ , the probability that the random structure contains a substructure tends to 1.

To use the above Lemma to study the 2-SAT sub-problem in NK landscapes, we view the random structure to be a random instance of N(n, 2, z), and W to be the set of all t-3-modules which are symmetric by their definitions(Sections 5 and 10, Franco & Gelder, 199). Theorem 4.3. If z = 2 + α > 2.837, then N ( n, 2, z ) is asymptotically insoluble with probability 1.

Let A t be the number of t-3-modules implied by N ( n, 2, z ) and t = O ( ln 2 n ).

Proof :
Theorem 4.2 shows that  lim E { A t } = ∞ . By Lemma 4.4, it is enough to show that for ech w E W

$$\sum_{w\in A\,(w)}P r\big{(}\bar{w}\mid w\,\big{)}=o\big{(}E\{A_{t}\}\big{)},$$
$$(4\cdot20)$$

where Pr(w | w) is the conditional probability that N(n, 2,z) implies the t-3-module w given that it implies w, and A ( w ) is the set of all t-3-modules sharing some clauses with w.

Suppose that w shares Q, 1 ≤ Q ≤ 2t clauses with w, and that these Q clauses are distributed among q 3-modules. Further, let q 1 be the number of 3-modules whose two clauses are both shared and q2 = q − q1 the number of 3-modules that only has one clause shared.

Let T 1 be a 3-module in w that shares exactly one clause with a 3-module T 2 in w.

We claim that the conditional probability that T 1 is implied by N ( n, 2, z ) given that w is