2. For any assignment s E {0,1}", we have fi(s)fj(s) = 0.

It is obvious that an instance of the NK decision problem is insoluble if there exists a pair of conflicting local fitness functions.

Based on the second moment method in the theory of probability (Alon & Spencer, 1992), we can prove the following upper bound result. As it takes linear time to check if there is a pair of conflicting local fitness functions, we can see that the fixed ratio model N(n, 2, z) is linearly solvable when z > 3.0.

Theorem 4.1. Define A to be the event that there is a conflicting pair of local fitness functions in N (n, 2, z). For the fixed ratio model N (n, 2, z) with z = 3.0 + ε, we have

$$\operatorname*{lim}_{n}P r\left\{A\right\}=1$$

and thus the problem is insoluble with probability asymptotic to 1.

Proof:   Without loss of generality, we may write f as where fi has 4 zeroes in its fitness value assignment for 1 ≤ i ≤ ε n , and 3 zeroes for ε n + 1 ≤ i ≤ n . Let I ij be the indicator function of the event that fi and fi conflicts with each other, i.e.,

$$I_{i j}=\left\{\begin{array}{l l}{{1,}}&{{\mathrm{if~}f_{i}\mathrm{~and~}f_{j}\mathrm{~conflicts~with~each~other;}}}\\ {{0,}}&{{\mathrm{else.}}}\end{array}\right.$$
j . We claim that  lim  P r { S = 0} = 0.
and S
By Chebyschev's inequality, we have

$$Pr\left\{S=0\right\}\leq Pr\left\{\left|S-E(S)\right|\geq E(S)\right\}\tag{4.3}$$ $$\leq\frac{Var(S)}{(E(S)^{2})}.$$

Since for each 1 ≤ i ≤ εn, fi has exactly 4 zeros in its fitness value assignment, we know that two local fitness function fit fj, 1 < i,j < en, conflict with each other if and only if they have exactly one common variable x such that one of the following is true: (1) fi(s) =
0(or 1), f i (s) = 1(or 0) for all the assignments s such that x = 1(respectively x = 0); and
(2) fi (s) = 1(or 0), fj (s) = 0(or 1) for all the assignments ssuch that x = 1(respectively x =
0);
Since the probability that two local fitness functions share at least one variable is equal to we have

$$1\,-\,{\frac{\left({\frac{n-2}{2}}\right)\left({\frac{n-4}{2}}\right)}{\left({\frac{n-1}{2}}\right)\left({\frac{n-1}{2}}\right)}},$$
$$Pr\left\{I_{ij}=1\right\}=\left(1-\frac{\binom{n-2}{2}\binom{n-4}{2}}{\binom{n-1}{2}\binom{n-1}{2}}\right)\cdot2\left(\frac{1}{\binom{8}{4}}\right)^{2}\tag{4.4}$$ $$=\Omega(\frac{1}{n}),\quad\varepsilon>0,\ \ 1\leq i,\,j\leq\varepsilon n,$$

317