(1) Each vertex v E V corresponds to a local fitness function; and

$$\mathrm{\boldmath~\ell~}f(x)\;=\;\sum_{i\,=\,1}^{n}\,f_{i}\big(x_{i}\,,\Pi\big(x_{i}\,\big)\big)\;\;\;b e\;\;a n$$

(2) There is an edge between vi, vi if and only if the corresponding local fitness functions fi, fi share variables, i.e., the neighborhoods Π(xi) and Π(xi) of xi and xi have a non-empty intersection, and both of them have at least one zero value.

Definition 3.2. Let f(x) =
ncction graph G = G(V,E).  Let G 1 , . . , G 1 be the connected components of G .  Since the vertices of G correspond to local fitness functions, we can regard Gi as a set of local fitness functions. For each 1 < i < l, let Ui C x = ( x 1 , . . , x n ) be the set of variables that appear in the definition of the local fitness functions in Gj.

It is easy to see that ( U 1 , . . . U i ) excluding independent vertices forms a disjoint partition of (a subset of) the variables x = ( x 1 , · · , x n ), and that the local fitness functions in G i only depend on the variables in U i . Furthermore, the NK decision problem is soluble if and only if for each 1 ≤ i ≤ l , there is an assignment si ∈ {0,1} l 0 / | to the variables in U i such that for each local fitness function g ∈ G i , g(s) = 1.

Theorem 3.1 summarizes the result on the uniform probability model.

Theorem 3.1. For any p(n) such that limp(n)n zk+T exists, k fixed,there is a polynomial time algorithm that successfully solves a random instance of N(n,k,p) with probability asymptotic to 1 as n tends to infinity.

Proof: We consider two cases: limp(n)n 7*** = + ∞ and limp(n)n 7*** < + ∞.

(1) The case of limp(n)n 2 **¹ = + ∞
Let Ai be the event that fi(y) = 0 for each possible assignment y E {0,1}*+1 and let A = U Ai be the event that at least one of the Ai's occurs. We have

 b = $\pi$. 
$$\begin{array}{r c l}{{\operatorname*{lim}_{n\,\rightarrow\,\infty}P r\left\{A\right\}}}&{{=}}&{{1-\operatorname*{lim}_{n\,\rightarrow\,\infty}P r\left\{\bigcap_{i\,=1}^{n}A_{i}^{c}\right\}}}\\ {{}}&{{}}&{{}}\\ {{}}&{{}}&{{=}}&{{1-\operatorname*{lim}_{n\,\rightarrow\,\infty}\left(1-p(n)^{2^{\,k+1}}\right)^{n}.}}\\ {{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}\end{array}$$
$$\leq\ \top$$
It can be shown that if k is fixed and lim p(n)n Tk+T = + ∞, then  lim Pr {A} = 1. It follows that with probability asymptotic to one, there is at least one local fitness function which takes on values 0 for any possible assignments. We can therefore show that in this case, the NK decision problem is insoluble by checking the local fitness functions one by one. And this only takes linear time.

(2) The case of limp(n)n 2*+1 < + ∞.

Consider an algorithm that first finds the connected components G i , 1 ≤ i ≤ l of the connection graph G of the NK model, and then uses brute force to find an assignment si E {0,1}l [] to the variables in Ui such that for each local fitness function g E Gi, g(s) = 1.  The time complexity of this algorithm is O(n 2 +n * 2 M(n,k,p)) where M(n, k, p) =
max(|U i |, 1 ≤ i ≤ l ) is the maximum size of the subsets ( U i , 1 ≤ i ≤ l ) associated with the