random models. In both of the models defined below, the neighborhood set Π( x i ) of a variable x i is selected by randomly choosing without replacement k = [ Π( x i )] variables from x \{xi}. Definition 2.1. The Uniform Probability Model N(n,k,p):  In this model, the fitness value of the local fitness function fi(xi,Π(xi)) is determined as follows: For each assignment y ∈ Dom ( fi ) = {0, 1} k +1, let fi ( y ) = 0 with the probability p and fi ( y ) = 1 with the probability 1 - p, where this is done for each possible assignment and each local fitness function independently.

Definition 2.2. The Fixed Ratio Model N(n,k,z):  In this model, the parameter z takes on values from [0, 2 k + 1 ]. If z is an integer, we specify the local fitness function fi ( x i , Π( x i ))
by randomly choosing without replacement z tuples of possible assignments Y = ( y 1, · · · y z )
from Dom ( fi ) = {0, 1}*+1, and defining the local fitness function as follows:

$$f_{i}(y)=\left\{\begin{array}{l l}{{0,}}&{{i f\;\;y\in Y\,;}}\\ {{1,}}&{{e l s\,e.}}\end{array}\right.$$

For a non-integer z = (1 − α)[ z ] + α[ z + 1] where [ z ] is the integer part of z, we choose randomly without replacement [(1 - α)n] local fitness functions and determine their fitness values according to N (n, k, [z]). The rest of the local fitness functions are determined according to N ( n, k, [ z ] + 1 ).

In the theory of random graphs, there are two related random models G(n,p) where each of the πίπ=11 possible edges is included in the graph independently with probability p, and G(n,m) where exactly m edges are chosen randomly and without replacement from the set of n [n,-]] possible edges. It is well known that for most of the monotone graph properties, results proved in G(n,p) (or G(n,m)) also hold asymptotically for G(n,Np)
(correspondingly, G(n, m)) where N = n(n,-ll, However, we cannot expect that similar relations exist between the two random models of NK landscapes defined above unless the parameter k tends to infinity. As a result, the asymptotic behaviors of the two NK landscape models are significantly different for fixed k .

We conclude this section by establishing a relation between the decision problem of NK
landscapes and the SAT problem. A decision problem of the NK landscape

$$f(x)=\sum_{i=1}^{n}f_{i}\left(x_{i}\,,\Pi\left(x_{i}\,\right)\right),$$

"is the maximum of f(x) equal or greater than n ?", can be reduced to a (k+1)-SAT problem as follows:
(1) For each local fitness function fi(xi,Π(xi)), construct a conjunction Ci = Λ Ci of clauses with exactly k + 1 variable-distinct literals from the set of variables { x i , Π( x i ) } ,
where z is the number of zero values that fi takes and C? is such that for any assignment y j E {0, 1} k +1 that falsifies C j , we have f j ( y j ) = 0.

(2) The (k+1)-SAT is the conjunction ϕ = Λ C i .

$$\varphi=\bigwedge_{i=1}C_{i}.$$
