Recall from Section 2 that each instance of N ( n, 2, z ) has an equivalent 3-SAT instance.

The idea is to show that with probability asymptotic to 1, an instance of N(n, 2,z) will contain a set of specially structured 3-clauses, called a t-3-module (Definition 10.3, Franco
& Gelder, 1998):

$\mathcal{M}=\{M_{1},\ldots,M_{3}p+2\},\;\;t=3p+2,$
where

$$M_{1}$$
$$\begin{array}{r l}{={}}&{{}\left({\bar{u}}_{1}\lor u_{2}\lor z_{1},{\bar{u}}_{1}\lor u_{2}\lor{\bar{z}}_{1}\right);}\end{array}$$
Mp-1 Mp Mp+1 ..
$$\begin{array}{c}{{M_{3p-1}}}\\ {{M_{3\,p}}}\\ {{M_{3p+1}}}\\ {{M_{3p+2}}}\end{array}$$
( Up-1 V Up V Zp-1; Up-1 V Up V Zp-1); l ( Up V Uo V zp, Up V Uo V Zp); l (Up+1 V Up+2 V Zp+1,Up+1 V Up+2 V Zp+1); l (U3p-1 VU3p V Z3p-1: U3p-1 VU3p V Z3p-1): (U3p Vuo Vz3p:U3p Vuo Vz3p) l (U0 V U1 V z3p+1; U0 V U1 V z3p+1); l (U0 V Up+1 V Z3p+2; U0 V Up+1 V Z3p+2); l
and u 1 , . . , u 3 p +1 , z 1 , . . , z p +1 are binary variables. Notice that a t-3-module can be reduced to a 2-SAT problem containing two contradictory cycles and hence is unsatisfiable.

The result is proved in two steps. In the first step, it is shown that for z > 2.837 the average number of t-3-modules contained in N ( n, 2, z ) tends to infinity as n increases. In the second step, we use a result established by Alon and Spencer (1992) on the second moment method to prove that for z > 2.837 the probability that N ( n, 2, z ) contains at least one t-3-module tends to 1.

Let us start with the first step to show that the average number of t-3-modules contained in N(n, 2, z) tends to infinity as n increases.

Definition 4.1. Given a t-3-module M and an NK landscape instance f = ∑ fi, k = 2, a sequence of local fitness functions

$$f_{i}\,,\,k=2,\,\,a$$

g = (91, is said to be a possible match(PM) if for each 1 ≤ m ≤ t, the main variable of gm is one of the three variables that occur in the 3-module Mm. A subsequence (h1, match g is legal if for any 1 ≤ m < j ≤ l,  h m ≠ h j .

  **Lemma 4.2**.: _Let $f(x)=\sum\limits_{i=1}^{n}f_{i}(x_{i},\Pi(x_{i}))$ be an instance of $N(n,2,z)$ and $\mathcal{M}$ be a $t$-$3$-module. Then the number of possible matches for the $t$-$3$-module $\mathcal{M}$ is $3^{!}$. Further, the 
number of legal possible matches is Θ ( ³ + √ √ √ √