%\documentstyle[jair,twoside,11pt,theapa]{article}
%\input epsf

\documentclass[11pt]{article}
%\input{PDFPreamble.tex}    % conditional choice of graphics driver
\usepackage{epsfig}
\usepackage[centertags]{amsmath}
\usepackage{amsthm}
\usepackage{jair}
\usepackage{theapa}
%------------------------------------------------------------------
\newtheorem{defn}{Definition}[section]
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}{Lemma}[section]
\newtheorem{conj}{Conjecture}[section]
\renewcommand{\theequation}{\thesection.\arabic{equation}}
%\newcommand{\text}[1]{\mbox{\rm #1}}
\newcommand{\con}[1]{{\cal C}(#1)}
%-------------------------------------------------------------------

\jairheading{17}{2002}{309-332}{06/02}{10/02}
\ShortHeadings{Phase Transition in NK Landscapes } {Gao \&
                Culberson}
\firstpageno{309}

\begin{document}
%\input{GraphicsEPSPDF.tex} % conditional graphics file extensions

\title{An Analysis of Phase Transition in NK Landscapes}

\author{\name  Yong Gao \email ygao@cs.ualberta.ca \\
       \name Joseph Culberson \email  joe@cs.ualberta.ca \\
       \addr  Department of Computing Science \\
                University of Alberta \\
                Edmonton, Alberta, Canada, T6G 2H1 \\
}

\maketitle

\begin{abstract}
 In this paper, we analyze the decision version of the
 NK landscape model from the perspective of threshold phenomena
 and phase transitions under two random distributions, the uniform
 probability model and the fixed ratio model. For the uniform
 probability model, we prove that the phase transition is easy in
 the sense that there is a polynomial algorithm that can solve a
 random instance of the problem with the probability asymptotic to
 1 as the problem size tends to infinity. For the fixed ratio
 model, we establish several upper bounds for the solubility
 threshold, and prove that random instances with parameters above
 these upper bounds can be solved polynomially. This, together
 with our empirical study for random instances generated below and in the
 phase transition region, suggests that the phase transition
 of the fixed ratio model is also easy.
\end{abstract}

\section{Introduction}
\label{Introduction}
 The {\sl NK landscape} is a fitness landscape model devised
 by \citeA{KAU89}. An appealing property of the NK landscape
 is that the ``ruggedness" of the landscape can be tuned by changing some
 parameters. Over the years, the NK landscape model itself has been studied
 from the perspectives of statistics and computational complexity
 \cite{WEI96,WTZ99}. In the study of genetic algorithms, NK landscape
 models have been used as a prototype and benchmark in the analysis of the
 performance of different genetic operators and the effects of different
 encoding methods on the algorithm's performance \cite{ALT96,HOR97,JON95}.

 In the field of combinatorial search and optimization, one of the
 interesting discoveries is the threshold phenomena and phase transitions.
 Roughly speaking, a phase transition in combinatorial
 search refers to the phenomenon that the probability that a random
 instance of the problem has a solution drops abruptly from 1 to 0 as
 the order parameter of the random model crosses a critical value
 called the {\sl threshold}. Closely related to this phase transition
 in solubility is the hardness of solving the problems. There has
 been strong empirical evidence and theoretical arguments showing
 that the hardest instances of the problems usually occur around the
 threshold and instances generated with parameters far away from
 the threshold are relatively easy. Since the seminal work of
 Cheeseman et al. \cite{CKT91}, many NP-complete combinatorial search
 problems have been shown to have the phase transition and the
 associated easy-hard-easy pattern
 \cite{CMI97,CUL01,FRE96,GMP98,KIS94,MSL92,VCU98}.


 In this paper, we analyze the NK landscape model from the
 perspective of threshold phenomena and phase transitions.
 We establish two random models for the decision problem of NK
 landscapes and study the threshold phenomena and the associated
 hardness of the phase transitions in these two models.

 The rest of the paper is organized as follows. In Section 2, we
 introduce the NK fitness landscape and our probabilistic models,
 the uniform probability model and the fixed ratio model.
 In Section 3 and Section 4, the threshold phenomena and phase
 transitions in NK landscapes are analyzed. For the uniform
 probability model, we prove that the phase transition of the uniform
 probability model is easy in the sense that there is a polynomial
 algorithm that can solve a random instance
 of the problem with the probability asymptotic to 1 as the problem size
 tends to infinity. For the fixed ratio model, we establish two upper
 bounds for the solubility threshold, and prove that random instances
 with parameters above these upper bounds can be solved polynomially.
 This, together with our empirical study for random instances generated
 below and in the phase transition region, suggests that the phase
 transition of the fixed ratio model is also easy. In Section 5, we
 report our experimental results on typical hardness of the fixed ratio
 model. In Section 6, we conclude our investigation and discuss
 implications of our results.

\section{NK Landscapes and their Probabilistic Models}
\label{nkModels}

An NK landscape
$
    f(x) = \sum\limits_{i=1}^{n}f_i(x_i, \Pi (x_i)),
$ is a real-valued function defined on binary strings of fixed
length, where $n > 0$ is a positive integer and $x = (x_1, \cdots
, x_n) \in \{0,1\}^n$. It is the sum of $n$ {\sl local fitness
functions} $f_i, \ 1\leq i \leq n$. Each local fitness function
$f_i(x_i, \Pi (x_i))$ depends on the {\sl main variable} $x_i$
and its neighborhood $\Pi (x_i)\subset {\cal P}_k( \{x_1, \cdots ,
x_n\}\backslash \{x_i\})$ where ${\cal P}_k(X)$ denotes the set
of all subsets of size $k$ from $X$. The most important parameters
of an NK landscape are the number of variables $n$, and the size
of the neighborhood $k = |\Pi (x_i)|$.

In an NK landscape, the neighborhood $\Pi (x_i)$ can be chosen in
two ways: the {\sl random neighborhood}, where the $k$
variables are randomly chosen from the set $\{x_1,\cdots
,x_n\}\backslash \{x_i\},$ and the {\sl adjacent neighborhood},
where $k$ variables with indices nearest to $i$ (modulo $n$) are
chosen. For example, for any even integer $k$, the $k$ variables
in $\Pi (x_i)$ can be defined as $x_{((n+i-\frac{k}{2}) \mod\
n)},\cdots, x_{((n+i+\frac{k}{2})\mod\ n)}.$ Once the
variables in the neighborhood are determined, the local fitness
function $f_i$ is determined by a fitness lookup table which
specifies the function value $f_i$ for each of the $2^{k+1}$
possible assignments to the variables $x_i$ and $\Pi (x_i)$.
%See\cite{ALT96} for a detailed discussion on the fitness lookup
%table.

Throughout this paper, we consider NK landscapes with random
neighborhoods. To simplify the discussion, we further assume that
the local fitness functions take on binary values. Given an NK
landscape $f$, the corresponding decision problem is stated as
follows: Is the maximum of $f(x)$ equal to $n$?  An NK landscape
decision problem is insoluble if there is no solution for it.

It has been proved  that the NK landscape model is NP complete
for $k \geq 2$ (\citeR<e.g., >{WEI96,WTZ99}). The proofs were
based on a reduction from SAT to the decision problem of NK
landscapes. To study the typical hardness of the NK landscape
decision problems in the framework of thresholds and phase
transitions, we introduce two random models. In both of the
models defined below, the neighborhood set $\Pi (x_i)$ of a
variable $x_i$ is selected by randomly choosing without
replacement $k = |\Pi (x_i)|$ variables from $x\backslash
\{x_i\}$.

\begin{defn}
\label{uniformDef}
 The Uniform Probability Model $\overline{N}(n,k,p)$:
 \ \ In this model, the fitness value of the
 local fitness function $f_i(x_i, \Pi (x_i))$ is determined as
 follows: For each assignment $y\in Dom(f_i)=\{0,1\}^{k+1}$,
 let $f_i(y)= 0$ with the probability $p$ and $f_i(y)= 1$ with the
 probability $1-p$, where this is done for each possible assignment and
 each local fitness function independently.
\end{defn}

\begin{defn}
\label{fixedRatioDef}
 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
 $f_i(x_i, \Pi (x_i))$ by randomly choosing without replacement $z$
 tuples of possible assignments $Y = (y_1, \cdots , y_z)$ from
 $Dom(f_i) = \{0,1\}^{k+1}$, and defining the local fitness function as
 follows:
 $$
           f_i(y)=\left\{\begin{array}{ll}
               0, & \text{if} \ \  y \in Y ; \\
               1, & \text{else}.
            \end{array}
            \right.
 $$
 For a non-integer $z = (1-\alpha)[z] + \alpha [z+1]$ where $[z]$ is
 the integer part of $z$, we choose
 randomly without replacement $[(1-\alpha) 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)$.
 \end{defn}
\par
In the theory of random graphs, there are two related random
models $G(n,p)$ where each of the $\frac{n(n-1)}{2}$ 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 $\frac{n(n-1)}{2}$ 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, \frac{m}{N})$)
where $N =\frac{n(n-1)}{2}$. 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$.
\par
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\limits_{i=1}^nf_i(x_i, \Pi (x_i)),
$$ ``is the maximum of $f(x)$ equal or greater than $n$?", can be
reduced to a (k+1)-SAT problem as follows:
\par
  (1) For each local fitness function $f_i(x_i, \Pi (x_i))$,
  construct a conjunction
  $C_i = \bigwedge\limits_{j = 1}^{z} C_i^j$
  of clauses with exactly $k+1$
  variable-distinct literals from the set of variables
  $\{x_i, \Pi (x_i)\}$,  where $z$ is the number of zero
  values that $f_i$ takes and $C_i^j$ is such that
  for any assignment $y_j\in \{0,1\}^{k+1}$ that falsifies $C_i^j$,
  we have $f_i(y_j) = 0$.
\par
(2) The (k+1)-SAT is the conjunction
       $ \varphi = \bigwedge\limits_{i = 1}^{n} C_i$.

\begin{table}
\begin{center}
\begin{tabular}{|c|c|c|c|c|} \hline
        $x$ &  $y$ & $z$ & $f_i$ &Clauses   \\ \hline
         0& 0& 0& 0& $x\vee y\vee z$ \\
         0& 0& 1& 1& \\
         0& 1& 0& 1& \\
         0& 1& 1& 0& $x\vee \bar{y}\vee \bar{z}$ \\
         1& 0& 0& 1& \\
         1& 0& 1& 0& $\bar{x}\vee y \vee \bar{z}$ \\
         1& 1& 0& 0& $\bar{x}\vee \bar{y} \vee z$ \\
         1& 1& 1& 1& \\
         \hline
\end{tabular}
\caption{A local fitness function and its equivalent 3-clauses. }
\end{center}
\end{table}

\noindent
Table 1 shows an example of the fitness assignment of
a local fitness  function $f_i = f_i(x, y, z)$ and its associated
equivalent 3-SAT clauses.
It is easy to see that for any assignment $s$ to the variables
$x, y, z$, $f_i(s) = 1$ if and  only if the assignment satisfies
the formula
$$ x\vee y\vee z, \ x\vee \bar{y}\vee \bar{z}, \
\bar{x}\vee y \vee \bar{z}, \ \bar{x}\vee \bar{y} \vee z.
$$


\section{Analysis of The Uniform Probability Model}
\label{uniformModel} In the uniform probability model
$\overline{N}(n,k,p)$, the parameter $p$ determines how many zero
values a local fitness function can take. We are interested in
how the solubility and hardness of the NK landscape decision
problem change as the parameter $p$ increases from 0 to 1. It
turns out that for fixed $p > 0$, the decision problem is
asymptotically trivially insoluble. This is quite similar to the
phenomena in the random models of the constraint satisfaction
problem observed by \shortciteA{AKK97}.
\par
To gain some more insight into the problem, we consider the case
where $p = p(n)$ is a function of the problem size $n$ with
$\lim\limits_{n}p(n) = 0$. Our analysis shows that the solubility
of the problem depends on how fast $p(n)$ decreases:

(1) If
\begin{equation}
\label{uniform01}
  \lim\limits_{n}p(n)n^{\frac{1}{2^{k+1}}} = +\infty,
\end{equation}
the problem is still asymptotically trivially insoluble because
with the probability asymptotic to 1, there is at least one local
fitness function that always has a fitness value 0;

(2) On the other
hand if $p(n)$ decreases fast enough, i.e.,
\begin{equation}
\label{uniform02}
\lim\limits_{n}p(n)n^{\frac{1}{2^{k+1}}} < +\infty,
\end{equation}
the problem can be decomposed into a set of independent
sub-problems. In either case the problem can be
solved in polynomial time. The case of
(\ref{uniform01}) is not difficult to prove, but to prove the
case of (\ref{uniform02}), we need to make use of the following
concepts and results.
\begin{defn}
 The {\sl connection graph} of an NK landscape instance
$f(x) = \sum\limits_{i=1}^nf_i(x_i, \Pi (x_i))$ is a graph $G =
G(V, E)$ satisfying

(1) Each vertex $v \in V$ corresponds to a local fitness
function; and

(2)There  is an edge between $v_i, v_j$ if and only if the
corresponding local fitness functions $f_i, f_j$ share variables,
i.e., the neighborhoods $\Pi (x_i)$ and $\Pi (x_j)$ of $x_i$ and
$x_j$ have a non-empty intersection, and both of them have at
least one zero value.
\end{defn}

\begin{defn}
Let $f(x) = \sum\limits_{i=1}^nf_i(x_i, \Pi (x_i))$  be an NK
landscape instance with the  connection graph $G = G(V, E)$. Let
$G_1, \cdots , G_l$ be the connected components of $G$. Since the
vertices of $G$ correspond to local fitness functions, we can
regard $G_i$ as a set of local fitness functions. For each $1\leq
i\leq l$, let $U_i \subset x = (x_1, \cdots , x_n)$ be the set of
variables that appear in the definition of the local fitness
functions in $G_i$.
\end{defn}

It is easy to see that $(U_1, \cdots U_l)$ excluding independent
vertices forms a disjoint partition of (a subset of) the
variables $x = (x_1, \cdots , 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\leq i\leq l$, there is an assignment $s_i\in
\{0,1\}^{|U_i|}$ to the variables in $U_i$ such that for each
local fitness function $g\in G_i$, $g(s) = 1$.

Theorem 3.1 summarizes the result on the uniform probability
model.
\begin{thm}
For any $p(n)$ such that $\lim\limits_{n}p(n)n^{\frac{1}{2^{k+1}}}$
exists, $k$ fixed,there is a polynomial time algorithm that successfully
solves a random instance of $\overline{N}(n,k,p)$
with probability asymptotic to 1 as n tends to infinity.
\end{thm}

{\sl Proof:}\ \ We consider two cases:
$\lim\limits_{n}p(n)n^{\frac{1}{2^{k+1}}} = +\infty$ and
$\lim\limits_{n}p(n)n^{\frac{1}{2^{k+1}}} < +\infty$.

(1) The case of $\lim\limits_{n}p(n)n^{\frac{1}{2^{k+1}}} = +\infty$.

 Let $A_i$ be the event that
 $f_i(y) = 0$ for each possible assignment $y \in \{0, 1\}^{k+1}$
 and let $A = \bigcup\limits_{i=1}^{n} A_i$ be the event that
 at least one of the $A_i$'s occurs. We have
 \begin{eqnarray*}
   \lim\limits_{n \rightarrow \infty}Pr\{A\}
           &=& 1 - \lim\limits_{n \rightarrow \infty}
                  Pr\{\bigcap\limits_{i=1}^{n} A_i^c\} \\
     &=& 1 - \lim\limits_{n \rightarrow \infty}(1-p(n)^{2^{k+1}})^n.
 \end{eqnarray*}
 It can be shown that if $k$ is fixed and
 $\lim\limits_{n}p(n)n^{\frac{1}{2^{k+1}}} = +\infty$, then
 $\lim\limits_{n \rightarrow \infty} 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 $\lim\limits_{n}p(n)n^{\frac{1}{2^{k+1}}} < +\infty$.

Consider an algorithm that first finds the connected components
$G_i, \ 1\leq i \leq l$ of the connection graph $G$ of the NK
model, and then uses brute force to find an assignment $s_i\in
\{0,1\}^{|U_i|}$ to the variables in $U_i$ such that for each
local fitness function $g\in G_i$, $g(s) = 1$. The time
complexity of this algorithm is $O(n^2+n*2^{\mathcal{M}(n, k,
p)})$ where $\mathcal{M}(n, k, p) = \max (|U_i|, 1\leq i\leq l)$
is the maximum size of the subsets $(U_i, 1\leq i\leq l)$
associated with the connected components of the connection graph.
To prove the theorem, we only need to show that $\mathcal{M}(n,
k, p) \in O(\log n)$. In the following, we will show that for
$\lim\limits_{n}p(n)n^{\frac{1}{2^{k+1}}} < +\infty$, we have $$
\lim\limits_{n\rightarrow \infty}Pr\{ \mathcal{M}(n,k,p)\leq
2^k+2\}=1 $$ Consider the connection graph $G = G(V, E)$ of the
NK model. It is a random graph and there is an edge between two
nodes if and only if the two corresponding local fitness
functions share variables and both of the local fitness functions
take at least one zero as their fitness value. However, under
this definition the edge probabilities are not independent. If
$vx \in E$ then we know that $f_x$ has at least one zero and so
the probability that $xw$ is in $E$ is greater than if there were
no other edge on $x$.

To deal with this we resort to the following proof construction. Let
$C_m = \{ v_1,\dots, v_m\}$ be a subset of $V$ of size $m$. Let $\pi$
be an  ordering (permutation) of $v_1 \dots v_m$. We say that
{\em $C_m$ is  variable connected with respect to the ordering $\pi$},
denoted as $\con{C_m,\pi}$, if for each $i, 2 \le i \le m$ there is
either
\begin{enumerate}
\item a $j < i$ such that $f_{\pi(j)}$ and $f_{\pi(i)}$ share a variable; or
\item a $j, 1\leq j \leq i$ such that the variable $x_j$
is one of the $k$ random variables in $f_i$.
\end{enumerate}

{\noindent{\bf Lemma}} {\em If the induced subgraph $G[C_m]$ is connected
then there exists at least one ordering $\pi$ of $v_1 \dots v_m$ such that
$\con{C_m,\pi}$.
}

As proof, consider the ordering of vertices
of any depth first search of a connected subgraph.
In this case, the connections are all by case 1.

The expected number of permutations $\pi$ for which
$\con{C_m,\pi}$ is $$ E_c = \mbox{\rm E}[ |\{\pi :
\con{C_m,\pi}\}|] = m! \mbox{\rm Pr}\{\con{C_m,\pi}\} $$ We then
observe that the expected number of connected induced graphs on
$m$ vertices is less than $p_0^m {n \choose m}E_c$, where $p_0$
is the probability that $f_i$ takes at least one  value zero. We
show this value goes to zero in the limit if $m \geq 2^k+2$.
Finally, since if there is a connected subgraph on $m$ vertices
then there must be one for each $i<m$, it follows that the
largest connected component has size at most $2^k+1$.

For a randomly generated permutation $\pi$ of $C_m$, let $C_i$ be
the set of the first $i$ vertices of the permutation. For $i\geq
2$ define $P_i$ to be the probability that $f_{\pi(i)}$ shares at
least one variable with $f_{\pi(j)}$ for some $j<i$ given that
$\con{C_{i-1},\pi /1, \cdots,i-1}$. Let $P_1 = 1$. (A one vertex
subgraph is always connected.)

For $i>1$ we have $P_i = \mbox{\rm Pr}\{ \exists j<i, f_{\pi(i)} $
and $f_{\pi(j)}$ share variables, given $\con{C_{i-1},\pi}$ or one
of the $k$ random variables in $f_{\pi(i)}$ is in $\{x_1 \dots
x_m\}-\{x_i\} \}$. $$ \mbox{\rm Pr}\{\con{C_m,\pi}\} =
\prod_{i=2}^m P_i. $$

Finally, for $i>1$ we note that $C_{i-1}$ has at most $(i-1)k$
distinct other variables. If $C_{i-1}$ is connected then the
number of variables may be less than this. Thus,
$$
P_i \leq  1 - \frac{{{n-k(i-1) -m}\choose k}} {{{n-1} \choose k}}.
$$
The combinatorial part reduces to
\begin{eqnarray*}
& & \frac{(n-k(i-1)-m) \dots (n-k(i-1)-m-k+1)}
    {(n-1) \dots  (n-k)} \\
& & \geq  \left( \frac{n-ki -m+1}{n-1} \right)^{k}.
\end{eqnarray*}
So, $\mbox{\rm Pr}\{ \con{C_m,\pi}\}$ is
\begin{eqnarray*}
 \  & \leq &
 \prod_{i=2}^m\left( 1 -\left( \frac{n-ki -m+1}{n-1}
    \right)^{k} \right) \\
&\leq &  \left( 1 - \left(1 - {\frac{km+m-2}{n-1}}
  \right)^{k}\right)^{m-1} \\
&\in &  O\left( \left( {\frac{1}{n}}\right)^{m-1} \right), m,k\  \mbox{\rm
fixed.}
\end{eqnarray*}
Noting that $p_0^m \in O\left( n^{ \frac{-m}{2^k+1}} \right)$,
we see that the expected number of connected subgraphs of size
$m$ is bounded by $$ p_0^m {n \choose m}E_c \in O\left( n^m
n^{\frac{-m}{2^k+1}} \left(\frac{1}{n} \right)^{m-1}\right) $$
which goes to zero if $m = 2^k+2$. It follows that
$\mathcal{M}(n,k,p)$ is less than $2^k+2$ with probability
asymptotic to 1. This completes the proof.

\section{Analysis of The Fixed Ratio Model}
\label{fixedRatioModel}
 As has been discussed in the previous section, the uniform probability
 model $\overline{N}(n,k,p)$ of NK landscapes is asymptotically trivial.
 Part of the cause of this asymptotic triviality  lies in the fact
 that if the parameter $p$ does not decrease very quickly with $n$,
 then asymptotically there will be at least one local fitness function
 that takes the value $0$
 for all the possible assignments, making the whole decision
 problem insoluble. In this section, we study the fixed ratio
 model $N(n,k,z)$. In this model, we require that each local
 fitness function has fixed number of zero values so that the
 trivially insoluble situation in the uniform probability model
 is avoided. We note that the same idea has been used in the study of the
 {\sl flawless CSP} \cite{GMP98}.

 Recall that in the fixed ratio model, we choose the
 neighborhood structure for each local fitness in the same way
 as in the uniform probability model $\overline{N}(n,k,p)$.
 To determine the fitness value for a local fitness function
 $f_i$, we randomly without replacement select exactly $z$ tuples
 $\{s_1, \cdots , s_z\}$ from $\{0,1\}^{k+1}$, and let
 $f_i(s_j) = 0$ for each $1\leq j \leq z$ and $f_i(s) = 1$ for
 every other $s\in \{0,1\}^{k+1}$.

 For the fixed ratio model, we are interested in how the
 probability of an instance of $N(n,k,z)$ being soluble
 changes as the parameter $z$ increases from $0$ to $2^{k+1}$.
 It is easy to see that the property ``There exists an
 assignment $x$ such that
 $f(x) = \sum\limits_{i=1}^nf_i(x_i, \Pi (x_i)) = n$"
 is monotone in the parameter $z$ --- the number of tuples at
 which a local fitness function takes zero.
 Actually, we have the following Lemma on the property of the
 solubility probability of the fixed ratio model:

 \begin{lem}
 For the fixed ratio model, if $z_1 > z_2$, then
 $$
    Pr\{N(n,k,z_1) \text{is soluble}\} \leq
    Pr\{N(n,k,z_2) \text{is soluble}\}.
 $$
 Furthermore, we have
 $$
  Pr\{N(n,k,z) \text{is soluble}\} =
  \left\{\begin{array}{ll}
             1, & \text{if}\ z \leq 1; \\
             0, & \text{if}\ z = 2^{k+1}.
            \end{array}
            \right.
 $$
 \end{lem}

Based on the above Lemma and in parallel to the study of the
threshold phenomena in other random combinatorial structures
such as 3-Coloring of random graphs and random 3-SAT,
we suggest the following conjecture:

\begin{conj}
\label{conj}
There exists a threshold $z_c$ such that
$$
  \lim\limits_{n\rightarrow \infty}Pr\{N(n,k,z) \text{is soluble}\} =
  \left\{\begin{array}{cc}
             1, & \text{if}\ z < z_c; \\
             0, & \text{if}\ z > z_c.
            \end{array}
            \right.
$$
\end{conj}

Conjectures like this are the starting point of the study of
phase transition in many random combinatorial structures such as
3-coloring of random graphs and random SAT, but the existence of
the thresholds is still an open question \cite{ACH99,CMI97}.
However, bounding the thresholds has been an important topic in
the study of phase transition
\cite{ACH99,ACH01,DUB01,FRG98,FRP83,FRS96,KKK98}. In this
section, we will establish two upper bounds on the threshold of
the parameter $z_c$, and theoretically prove that random
instances generated with the parameter $z$ above these upper
bounds can be solved with probability asymptotic to 1 by
polynomial (even linear) algorithms.

Characterizing the sharpness
of the thresholds is also of great interest in the study of
the phase transition. After proving that every monotone graph
property has a threshold behavior \cite{FRK96},  \citeA{FRI99}
established a necessary and sufficient condition for a monotone
graph property to have sharp threshold, which has been
used to prove the sharpness of the thresholds of 3-colorability
and 3-SAT problems \cite{FRI99,ACH99}. For the fixed ratio model
discussed in this paper, we  suspect that it will exhibit a
coarse threshold behavior, and would like to leave a detailed
investigation into this problem as a future research direction.

\subsection{The Upper Bound of $z = 3.0$ }
\label{3.0BoundSubsect}
 The derivation of this upper bound is based on the concept
 of a {\sl conflicting pair} of local fitness functions.
 We say that two local fitness functions $f_i$ and
 $f_j$ conflict with each other if
\begin{enumerate}
\item$f_i$ and $f_j$ share at least one variable $x$; and
\item For any assignment $s\in \{0,1\}^n$, we have
 $f_i(s)f_j(s) = 0$.
\end{enumerate}
 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
 \cite{ALS92}, 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$.

\begin{thm}
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 + \varepsilon$, we have
$$ \lim\limits_{n}Pr\{ A \} = 1 $$
and thus the problem is insoluble with probability asymptotic to 1.
\end{thm}

{\sl Proof:} \ \ Without loss of generality, we may write $f$
 as where $f_i$ has 4 zeroes in  its fitness value assignment for
 $1\leq i\leq \varepsilon n$, and 3 zeroes for $\varepsilon n+1\leq
 i\leq n$. Let $I_{ij}$ be the indicator function of the event
 that $f_i$ and $f_j$ conflicts with each other, i.e.,
$$
  I_{ij} =
  \left\{\begin{array}{cl}
             1, & \mbox{if $f_i$ and $f_j$ conflicts with each other} ; \\
             0, & \mbox{else}.
            \end{array}
            \right.
$$
and $S = \sum\limits_{1\leq i, j\leq \varepsilon n} I_{ij}$. We
claim that $\lim\limits_{n\rightarrow \infty}Pr\{S = 0\} = 0$.

By Chebyschev's inequality, we have
\begin{equation}
\begin{split}
  Pr\{S=0\} &\leq Pr\{|S-E(S)|\geq E(S)\} \\
            &\leq \frac{Var(S)}{(E(S)^2)}.
\end{split}
\end{equation}
Since for each $1\leq i\leq \varepsilon n, f_i$  has exactly 4
zeros in its fitness value assignment, we know that two local
fitness function $f_i, f_j, 1\leq i, j \leq \varepsilon n$,
conflict with each other if and only if they have exactly
one  common variable $x$ such that one of the following is true:
(1)$f_i(s) = 0(\mbox{or}\ 1), f_j(s) = 1(\mbox{or}\ 0)$
 for all the assignments $s$ such that
 $x = 1(\mbox{respectively}\ x = 0)$; and
(2)$f_i(s) = 1(\mbox{or}\ 0),f_j(s) = 0(\mbox{or}\ 1)$
 for all the assignments $s$ such that
   $x = 1(\mbox{respectively}\ x = 0)$;

Since the probability that two local fitness functions share at
least  one variable is equal to $$
  1 -
  \frac{\binom{n-2}{2}\binom{n-4}{2}}{\binom{n-1}{2}\binom{n-1}{2}},
$$
we have
\begin{equation}
\begin{split}
  Pr\{I_{ij}=1\} &=
      \left(1 -
      \frac{\binom{n-2}{2}\binom{n-4}{2}}
            {\binom{n-1}{2}\binom{n-1}{2}}\right)
      \cdot 2\left(\frac{1}{\binom{8}{4}}\right)^2 \\
    &= \Omega(\frac{1}{n}),
           \ \ \ \varepsilon > 0, \ \ 1\leq i, j \leq \varepsilon n,
\end{split}
\end{equation}
and hence,
$$
 E(S) = \sum\limits_{1\leq i,j\leq \varepsilon n}E(I_{ij})
  =\sum\limits_{1\leq i,j\leq \varepsilon n}Pr\{I_{ij} = 1\}
  \in \Omega(n).
$$
We now consider the variance of $S$. Since
$S = \sum\limits_{1\leq i, j\leq \varepsilon n} I_{ij}$, we have
$$
 Var(S) = \frac{\sum\limits_{i,j}Var(I_{ij}) +
            2\sum\limits_{(i,j)\neq (l,m)}[E\{I_{ij}I_{lm}\}
                  -E\{I_{ij}\}E\{I_{lm}\}]}
           {(E(S))^2}.
$$
Let
$$
A_1 =\frac{\sum\limits_{i,j}Var(I_{ij})} {(E(S))^2}
$$
and
$$
A_2 = \frac{2\sum\limits_{(i,j)\neq (l,m)}[E\{I_{ij}I_{lm}\}-
        E\{I_{ij}\}E\{I_{lm}\}]}
        {(E(S))^2}.
$$
It is easy to see that $\lim\limits_{n\rightarrow \infty}A_1 = 0$. To prove
$\lim\limits_{n\rightarrow \infty}A_2 = 0$, we consider two cases:

{\bf Case 1: $i\neq j\neq m\neq l$.}\ \ In this case, the two random
variables $I_{ij}$ and $I_{lm}$ are actually independent. It
follows that $E\{I_{ij}I_{lm}\} - E\{I_{ij}\}E\{I_{lm}\} = 0$.

{\bf Case 2: $(i,j)\neq (l,m)$}, but they have one in common,
say $j = l$. In this case, we have
\begin{eqnarray*}
   E\{I_{ij}I_{lm}\} - E\{I_{ij}\}E\{I_{lm}\}
  &=&Pr\{I_{ij} = 1\}Pr\{I_{jm}= 1|I_{ij} = 1\} -
           \Omega\left(\left(\frac{1}{n}\right)^2\right) \\
  &=& \Omega\left(\frac{1}{n}\right)Pr\{I_{jm}= 1|I_{ij} = 1\} -
           \Omega\left(\left(\frac{1}{n}\right)^2\right)
\end{eqnarray*}
Given that $f_i$ and $f_j$ conflict with each other, the
conditional probability that $f_j$ and $f_m$ conflict with each other
is still in $\Omega(\frac{1}{n})$.
\par
Since there are only
$ C_{\varepsilon n}^{3}$  pairs of $ I_{ij}$ and $I_{jm}$ satisfying
the condition in Case 2,
we know that
$ \sum\limits_{(i,j)\neq (l,m)}
  [E\{I_{ij}I_{lm}\}- E\{I_{ij}\}E\{I_{lm}\}]$
is in $\Omega(n)$. And therefore,
$
 \lim\limits_{n\rightarrow \infty} A_2 = 0.
$
It follows that
$$
 \lim\limits_{n\rightarrow \infty}Pr\{S=0\} \leq
  \lim\limits_{n\rightarrow \infty}\frac{Var(S)}{(E(S)^2)} = 0.
$$
Since the event $\{S > 0\}$  implies that there exists a
conflicting pair of local fitness functions, the theorem
follows. \ \ \ $\qed$

\subsection{2-SAT Sub-problems in $N(n,2,z)$ and a Tighter Upper Bound}
\label{2satSubsection}
In this subsection, we establish a tighter upper bound $z>2.837$ for the
threshold of the fixed ratio model $N(n,2,z)$ by showing that
asymptotically $N(n,2,z)$ contains an unsatisfiable
2-SAT sub-problem with probability 1 for any value of $z$ greater
than 2.873. This also gives us a polynomial time algorithm which
determines that $N(n,2,z)$ is insoluble with probability asymptotic
to 1 for $z>2.837$.

 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,  \citeR{FRG98}):
\begin{eqnarray*}
\mathcal{M}  =  \{ M_1, \dots , M_{3p+2} \}, \ \ t = 3p + 2,
\end{eqnarray*} where
\begin{eqnarray*}
M_1  & = &  (\bar{u}_1\vee u_2\vee z_1,
\bar{u}_1\vee u_2\vee \bar{z}_1); \\
\, \, \, \, \, \, \, \, \, \cdots \\
M_{p-1} & = & (\bar{u}_{p-1}\vee u_p\vee z_{p-1},
\bar{u}_{p-1}\vee u_p\vee \bar{z}_{p-1});  \\
M_{p} & = & (\bar{u}_{p}\vee \bar{u}_{0}\vee z_{p},
\bar{u}_{p}\vee \bar{u}_{0}\vee
\bar{z}_{p}); \\
M_{p+1} & = & (\bar{u}_{p+1}\vee u_{p+2}\vee z_{p+1},
\bar{u}_{p+1}\vee u_{p+2}\vee \bar{z}_{p+1}); \\
\, \, \, \, \, \, \, \, \, \cdots \\
M_{3p-1} & = & (\bar{u}_{3p-1}\vee u_{3p}\vee z_{3p-1},
\bar{u}_{3p-1}\vee u_{3p}\vee \bar{z}_{3p-1}); \\
M_{3p} & = & (\bar{u}_{3p}\vee u_{0}\vee z_{3p},
\bar{u}_{3p}\vee u_{0}\vee \bar{z}_{3p})  \\
M_{3p+1} & = &  (\bar{u}_0\vee u_1\vee z_{3p+1},
\bar{u}_0\vee u_1\vee \bar{z}_{3p+1}); \\
M_{3p+2} & = & (u_0\vee u_{p+1}\vee z_{3p+2}, u_0\vee u_{p+1}\vee
\bar{z}_{3p+2});
\end{eqnarray*}
and  $u_1, \cdots , u_{3p+1}, z_1, \cdots , z_{3p+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 \citeA{ALS92} 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.

 \begin{defn}
 Given a t-3-module $\mathcal{M}$ and an NK landscape instance
 $f = \sum\limits_{i=1}^{n}f_i, k = 2$, a sequence of local fitness
 functions
 $$
   \mathbf{g}=(g_1, \cdots , g_t) \subset (f_1, \cdots , f_n)
 $$
 is said to be a {\sl possible match}(PM) if for each
 $1\leq m\leq t$, the main variable of $g_m$ is  one of the
 three variables that occur in the 3-module $M_{m}$.
 A subsequence $(h_1, \cdots , h_l)$ of a possible match $\mathbf{g}$
 is legal if for
 any $1\leq m < j\leq l, \ \  h_m \neq h_j$.
\end{defn}
\par

\begin{lem}
\label{matchLemma}
 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^t$. Further, the number of legal
 possible matches is
  $\Theta\left((\frac{3+\sqrt{5}}{2})^t \right)$.
\end{lem}
\par
\noindent
{\sl Proof}:\ \  For each $1\leq m\leq t$, there are exactly 3
 possible choices for $g_m$:
 $$
 f_{i_1}(x_{i_1}, \Pi (x_{i_1})), f_{i_2}(x_{i_2}, \Pi (x_{i_2})),
 f_{i_3}(x_{i_3}, \Pi (x_{i_3})),
 $$
 where $x_{i_1}, x_{i_2}, {\text and} \ \ x_{i_3}$
 correspond to the three variables that occur in the 3-module
 $M_m$. Therefore, there are $3^t$ possible matches for the
 t-3-module.

To prove the second conclusion, we divide the t-3-module into 3
parts $\mathcal{M} = (\mathcal{M}_1, \mathcal{M}_2,
\mathcal{M}_3)$,  where $\mathcal{M}_1 = (M_{m}, 1\leq m \leq
p)$,\ \ $\mathcal{M}_2 = (M_{m}, p+1\leq m \leq 3p-1)$, \ and
$\mathcal{M}_3 = (M_{3p}, M_{3p+1}, M_{3p+2})$. Letting $L_1,
L_2, and\ L_3$ be the number of legal possible matches for
$\mathcal{M}_1, \mathcal{M}_2, \mathcal{M}_3$ respectively. Since
the literals in $\mathcal{M}_1$ are variable-distinct from the
literals in $\mathcal{M}_2$, we have that the number of legal
possible matches, $L$,  for the t-3-module $\mathbf{M}$ satisfies
$$
   L_1L_2 \leq L \leq 27L_1L_2.
$$
 We now estimate the order of $L_1$.
 To this end, we consider the probability space
 $(\Omega, P)$, where $\Omega$ is the set of
 sequences $(g_1, \cdots ,g_p)$  of local fitness functions that
 possibly match $\mathcal{M}_1$ and
 $P$ is the uniform probability distribution. Then, the number
 of legal possible matches is
\begin{equation}
\label{matchLemmaEQ01}
    L_1 = |\Omega|\cdot Pr\{\text{a random sample from} \ \Omega
         \ \ \text{is legal}\}
\end{equation}
 Let $\mathbf{g}=(g_1,\cdots , g_p)$ be a random sample from $\Omega$
 and $x_{g_m}$ denote the main variable of the local fitness
 function $g_m$, then we have
$$
 Pr\{x_{g_m}=|u_{m}|\} = Pr\{x_{g_m}=|u_{m+1}|\}
             =Pr\{x_{g_m}=|z_m|\} = \frac{1}{3},
$$
where $|u|$ denotes the  variable corresponding to the literal $u$.
\par
Let $B_m, 0<m \leq p$ be the event that
the first $m$ local fitness functions $g_1, \cdots , g_m$ in
the possible match
$\mathbf{g}=(g_1,\cdots , g_p)$  are mutually distinct. Since
in $\mathcal{M}_1$ only consecutive 3-modules share variables, we have
$$
  B_m =
  \{(g_1, \cdots,  g_m):\ g_i \neq g_{i+1},\ 1\leq i\leq m-1\}.
$$
Let
 $b_m = Pr\{g_{m} \neq g_{m-1}\mid B_{m-1}\}, m \geq 2 $, \ and
 $b_1 = 1$. Notice that $B_1 = \Omega$. Then, we have
\begin{equation}
\label{matchLemmaEQ02}
\begin{split}
& Pr\{\mathbf{g}=(g_1,\cdots , g_p) \text{is legal}\} = Pr\{B_p\}  \\
&=Pr\{g_1\neq g_2, g_2\neq g_3,\cdots , g_{p-1}\neq g_p\} \\
&= Pr\{B_1\}Pr\{g_2\neq g_1 \mid B_1\}\cdot
            Pr\{g_3\neq g_2\mid B_2\}\cdots
            Pr\{g_{p}\neq g_{p-1}\mid B_{p-1}\} \\
&= b_1 b_2\cdots b_p \\
\end{split}
\end{equation}
Recalling that $x_{g_m}$ denotes the main variable of the local
fitness function $g_m$,  we have
\begin{eqnarray}
\label{matchLemmaEQ03}
  b_p &=& Pr\{g_{p-1}\neq g_p, x_{g_{p-1}}=|u_{p}|\mid B_{p-1}\} +
          Pr\{g_{p-1}\neq g_p, x_{g_{p-1}}\neq|u_{p}|\mid B_{p-1}\}
                         \nonumber \\
      &=& Pr\{g_{p-1}\neq g_p\mid B_{p-1}, x_{g_{p-1}}=|u_{p}|\}\cdot
            Pr\{x_{g_{p-1}}=|u_{p}|\mid B_{p-1}\} +  \nonumber \\
  & & \, \, \, \, \, \,
         Pr\{g_{p-1}\neq g_p\mid B_{p-1}, x_{g_{p-1}}\neq |u_{p}|\}\cdot
            Pr\{x_{g_{p-1}}\neq |u_{p}|\mid B_{p-1}\}  \nonumber \\
      &=& \frac{2}{3}a_p + (1-a_p) \nonumber \\
      &=& 1-\frac{1}{3}a_p,
\end{eqnarray}
where $a_p = Pr\{x_{g_{p-1}}=|u_{p}|\mid B_{p-1}\}$. For $a_p$, we have
\begin{equation}
\label{matchLemmaEQ04}
\begin{split}
 a_p &= \frac{Pr\{B_{p-1}, x_{g_{p-1}}=|u_{p}|\}}{Pr\{B_{p-1}\}}  \\
     &= \frac{1}{Pr\{B_{p-1}\}}
         ( Pr\{B_{p-1}, x_{g_{p-1}}=|u_{p}|,x_{g_{p-2}}=|u_{p-1}|\}  \\
     &  \quad \quad + Pr\{B_{p-1}, x_{g_{p-1}}=|u_{p}|,
               x_{g_{p-2}}\neq |u_{p-1}|\})
           \\
   &= \frac{1}{Pr\{B_{p-1}\}}(
       Pr\{x_{g_{p-1}}=|u_{p}|\mid B_{p-1}, x_{g_{p-2}}=|u_{p-1}|\}\cdot
         Pr\{B_{p-1}, x_{g_{p-2}}=|u_{p-1}|\}  \\
       &\quad \quad +
         Pr\{x_{g_{p-1}}=|u_{p}|\mid B_{p-1},
             x_{g_{p-2}}\neq |u_{p-1}|\}\cdot
          Pr\{B_{p-1}, x_{g_{p-2}}\neq |u_{p-1}|\}
           )  \\
   &= \frac{1}{Pr\{B_{p-1}\}}\left(
         \frac{1}{2}Pr\{B_{p-1}, x_{g_{p-2}}=|u_{p-1}|\} +
         \frac{1}{3} Pr\{B_{p-1}, x_{g_{p-2}}\neq |u_{p-1}|\}
         \right) \\
\end{split}
\end{equation}
The last equation in the above formula is because that given
$B_{p-1}$ and $ x_{g_{p-2}} = |u_{p-1}|$ (or $x_{g_{p-2}}\neq |u_{p-1}|$),
we have two (three, respectively) choices in selecting the local
fitness function $g_{p-1}$. Consider the two terms
$Pr\{B_{p-1}, x_{g_{p-2}}=|u_{p-1}|\}$ and
$Pr\{B_{p-1}, x_{g_{p-2}}\neq |u_{p-1}|\}$ in (\ref{matchLemmaEQ04}),
we have
\begin{equation}
\label{matchLemmaEQ05}
\begin{split}
 & Pr\{B_{p-1}, x_{g_{p-2}}=|u_{p-1}|\}  \\
 &= Pr\{g_{p-2}\neq g_{p-1} \mid B_{p-2},
       x_{g_{p-2}} = |u_{p-1}|\} \cdot Pr\{B_{p-2}, x_{g_{p-2}}
          = |u_{p-1}|\} \\
 &= \frac{2}{3}\Pr\{x_{g_{p-2}} = |u_{p-1}|\mid B_{p-2}\}
           \cdot Pr\{B_{p-2}\} \\
 &=  \frac{2}{3}a_{p-1}\cdot Pr\{B_{p-2}\} \\
\end{split}
\end{equation}
and
\begin{equation}
\label{matchLemmaEQ06}
\begin{split}
 & Pr\{B_{p-1}, x_{g_{p-2}}\neq |u_{p-1}|\}  \\
 &= Pr\{g_{p-2}\neq g_{p-1} \mid B_{p-2},
       x_{g_{p-2}} \neq |u_{p-1}|\} \cdot Pr\{B_{p-2}, x_{g_{p-2}}
          \neq |u_{p-1}|\} \\
 &= Pr\{x_{g_{p-2}} \neq |u_{p-1}|\mid B_{p-2}\}
           \cdot Pr\{B_{p-2}\} \\
 &=(1-a_{p-1})\cdot Pr\{B_{p-2}\} \\
\end{split}
\end{equation}
By plugging (\ref{matchLemmaEQ05}) and (\ref{matchLemmaEQ06})
into (\ref{matchLemmaEQ04}), we get
$$
 a_p = \frac{Pr\{B_{p-2}\}}{Pr\{B_{p-1}\}}\left(
         \frac{1}{3}a_{p-1} + \frac{1}{3}(1-a_{p-1})\right)
     = \frac{1}{3b_{p-1}}.
$$
This, together with (\ref{matchLemmaEQ03}), gives us
\begin{equation}
\label{matchLemmaEQ07}
 b_p = 1 - \frac{1}{9b_{p-1}}.
\end{equation}
It is not difficult to show that the sequence $\{b_p\}$ is
decreasing and lower bounded by 0. Letting $\lim\limits_{p}b_p =
b$ and taking the limit on both sides, we get
\begin{equation}
\label{matchLemmaEQ08}
 b = 1-\frac{1}{9b},
\end{equation}
and thus, $b = \frac{3\pm\sqrt{5}}{6}$. In our case,
$b= \frac{3+\sqrt{5}}{6}$ since $b_1 = 1$. It follows that
$b_p \geq b= \frac{3+\sqrt{5}}{6}$ and thus,
$$
   b_1\cdots b_p \geq \left(\frac{3+\sqrt{5}}{6}\right)^p.
$$
From (\ref{matchLemmaEQ01}), we know that the number of legal
possible matches is greater than
\begin{equation}
\label{matchLemmaEQ09}
  3^p\left( \frac{3+\sqrt{5}}{6}\right)^p =
     \left( \frac{3+\sqrt{5}}{2}\right)^p.
\end{equation}
To prove  that the expected number of legal possible matches $L_1$ for
$\mathcal{M}_1$ is in
$\Theta \left( \left (\frac{3+\sqrt{5}}{2}\right )^p \right)$, let
$\alpha_p = b_p - \frac{3+\sqrt{5}}{6} = b_p -b $.
From (\ref{matchLemmaEQ07}) and (\ref{matchLemmaEQ08}), we have
$$
  \alpha_p = b_p -b = \frac{b_{p-1} - b}{9bb_{p-1}} \leq
             d\alpha_{p-1}, \ \ 0< d < 1,
$$
which means that the series $\sum\limits_{m = 1}^{p}\alpha_m$ is
convergent. It follows that
$$
   (1+\frac{\alpha_1}{b})\cdots (1+\frac{\alpha_p}{b})
$$
converges to a finite positive constant $c$. Therefore,
\begin{equation}
\begin{split}
  b_1\cdots b_p &= (b+\alpha_1) \cdots (b+\alpha_p) \\
                &= b^p
                 \left(1+\frac{\alpha_1}{b}\right)\cdots
                  \left(1+\frac{\alpha_p}{b}\right)  \\
                &\leq c\left(\frac{3+\sqrt{5}}{6}\right)^p \\
\end{split}
\end{equation}
for sufficient large $p$ and some constant $c$.
\par
Similarly, we can show that the number of legal possible matches
$L_2$ for $\mathcal{M}_2$ is in $\Theta \left( \left
(\frac{3+\sqrt{5}}{2}\right )^{2p + 2} \right)$. Recalling that
the number of legal possible matches $L$ for the t-3-module
satisfies $L_1L_2 \leq L \leq 27L_1L_2$, the second conclusion
follows. $\qed$
\par
The following Lemma calculates the probability that a matching
local fitness function implies the matched 3-module.
\par
\begin{lem}
\label{3moduleLemma}
Given a 3-module $x\vee y\vee w, \ x\vee y\vee \bar{w}$, and a
local fitness function $g$ such that the main variable $x_g$ of
$g$ is one of the three Boolean variables $ |x|, |y|, |w|$, let
$z = 2 + \alpha, \ 0\leq \alpha \leq 1$ be the parameter in the
fixed ratio model $N(n,2,z)$. Then the probability that $g$
contains the 3-module is
\begin{equation}
p_0 = \left(\frac{1}{\binom{n-1}{2}}\right)
      \left(\frac{1}{28}(1-\alpha) + \frac{6}{56}\alpha\right)
\end{equation}
\end{lem}

{\sl Proof}: \ \ Since $x_g$ is already one of the variables in
the 3-module, the probability that the other two variables are
also in the 3-module is $\frac{1}{\binom{n-1}{2}}$.
\par
Now, assume that the variables of the local fitness function $g$ are
the same as the variables in the 3-module. From the definition of
the fixed ratio model, $g$ has two
zeros in its fitness value assignment with probability $(1-\alpha)$,
and has three zeros in its fitness assignment with probability
$\alpha$. Note that the local fitness function $g$ implies the
3-module $x\vee y\vee w, \ x\vee y\vee \bar{w}$
if and only if
$$
 g(\bar{x}, \bar{y}, \bar{w}) = 0 \ \ \text{and} \ \ \
 g(\bar{x}, \bar{y}, w) = 0.
$$
From the definition of the fixed ratio model, this happens with
the probability
$$
    \frac{1}{\binom{8}{2}}(1-\alpha) + \frac{6}{\binom{8}{3}}
      \alpha
$$
The Lemma follows. \ \ \ $\qed$

With the above preparation, we can now prove that the average number
of t-3-modules contained in $N(n,2,z)$ tends to infinity.

\begin{thm}
\label{averageModuleThm}
Let $A_t$ be the number of t-3-modules contained in $N(n,2,z)$ and
$t = \Theta (\ln^2 n)$. Then, if $z=2+\alpha > 2.837$,
\begin{equation}
\label{averageModuleThmEQ01}
 \lim\limits_{n\rightarrow \infty}E\{A_t\} = \infty.
\end{equation}
\end{thm}

{\sl Proof}: \ \ From Lemma \ref{matchLemma}, there are more than
$(\frac{3+\sqrt{5}}{2})^t$ legal possible matches for a fixed
t-3-module. From Lemma \ref{3moduleLemma}, we know that  each possible legal
match $\mathbf{g} = \{g_1, \cdots , g_t\}$ implies the t-3-module
with probability $p_0^t$. From the proof of Theorem 10.1 in
\cite{FRG98}, there are
\begin{equation}
\label{averageModuleThmEQ02}
 2^{t-2}n^{\underline{t-1}}(n-t+1)^t
\end{equation}
possible t-3-modules, where
$n^{\underline{t-1}} = \frac{n!}{(n-t+1)!}$.
Let $r = \left(\frac{1}{28}(1-\alpha) +
\frac{6}{56}\alpha\right)$, and write
$p_0 = \frac{1}{\binom{n-1}{2}}r$.
We have
\begin{equation}
\label{averageModuleThmEQ03}
\begin{split}
  E\{A_t\}
     &=\left(\frac{3+\sqrt{5}}{2}p_0\right)^t\cdot
         2^{t-2}n^{\underline{t-1}}(n-t+1)^t   \\
     &= \left(\frac{3+\sqrt{5}}{2}r\right)^t\cdot
              2^{t-2}n^{\underline{t-1}}(n-t+1)^t\cdot
                  \frac{1}{\binom{n-1}{2}^t} \\
     &= \frac{1}{4(n-t+1)}\left(\frac{3+\sqrt{5}}{2}r\right)^t\cdot
         \frac{2^{t}n^{\underline{t}}(n-t+1)^t}
                 {\binom{n}{2}^{t}}
         \left(\frac{\binom{n}{2}}{\binom{n-1}{2}}\right)^t \\
     &= \frac{1}{4(n-t+1)}\left(\frac{3+\sqrt{5}}{2}r\right)^t\cdot
         \frac{4^{t}n^{\underline{t}}(n-t+1)^t}
                 {(n(n-1))^{t}}
         \left(\frac{n}{n-2}\right)^t \\
     &=\frac{1}{4n}(2(3+\sqrt{5})r)^t
        (1-O\left(\frac{t^2}{n}\right)), \\
\end{split}
\end{equation}
where the fourth equation in (\ref{averageModuleThmEQ03}) is due to the fact that
for any positive integer n and q such that $q < \frac{n}{2}$,
we have $n^qe^{-q^2/2n}\leq n^{\underline{q}} \leq n^q $. It follows that
$\lim\limits_{n\rightarrow \infty}E\{A_t\} = \infty$ if
\begin{equation}
\label{averageModuleThmEQ04}
2(3+\sqrt{5})r > 1.
\end{equation}
Solving the inequality (\ref{averageModuleThmEQ04})
gives us $\alpha > 0.837$, that is,
$z = 2 + \alpha > 2.837$. This proves Theorem \ref{averageModuleThm}.
\ \ \ $\qed$

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, \citeR{FRG98}) to apply the second moment
method \cite{ALS92}:
\begin{lem}
\label{ALSLemma} (\citeR{ALS92}, 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\in W$. Let $I_w = 1$
when $w$ is in the random structure and 0 otherwise. If
\par
 (1) elements of $W$ are symmetric;
\par
(2) $\mu = E\{\sum\limits_{w\in W}I_w\}\rightarrow \infty$; and
\par
(3) $\sum\limits_{\bar{w}\in A(w)}Pr(\bar{w}\mid w)
      = o(\mu)$,\ \ for each $w\in W$,
\par
\noindent
then as $n\rightarrow \infty$, the probability that the random
structure contains a substructure tends to 1.
\end{lem}

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, \citeR{FRG98}).

\begin{thm}
\label{probabOneThm}
If $ z = 2+ \alpha > 2.837$, then $N(n,2,z)$ is asymptotically
insoluble with probability 1.
\end{thm}
\par
\noindent
{\sl Proof}: \ \ Let $A_t$ be the number of t-3-modules implied by
$N(n,2,z)$ and $t = O(\ln^2 n)$. Theorem \ref{averageModuleThm}
shows that
$\lim\limits_{n\rightarrow \infty}E\{A_t\} = \infty$.
By Lemma \ref{ALSLemma}, it is enough
to show that for each $w\in W$,
\begin{equation}
\label{probabOneThmEQ01}
\sum\limits_{\bar{w}\in A(w)}Pr(\bar{w}\mid w) = o(E\{A_t\}),
\end{equation}
where $Pr(\bar{w}\mid w)$ is the conditional probability that
$N(n,2,z)$ implies the t-3-module $\bar{w}$ given that it
implies $w$, and $A(w)$ is the set of all t-3-modules sharing some
clauses with $w$.
\par
Suppose that $\bar{w}$ shares $Q, 1\leq Q\leq 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 $q_2 = q-q_1$ the  number of 3-modules that
only has one clause shared.
\par
Let $T_1$ be a 3-module in $\bar{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 implied by $N(n,2,z)$, is
\begin{equation}
\label{probabOneThmEQ02}
 \frac{1}{6}\alpha + O(\frac{1}{n}).
\end{equation}
Without loss of generality, assume that $T_2 = \{x\vee y\vee u,
x\vee y\vee \bar{u}\}$ and $T_1 = \{x\vee y\vee u, \bar{x}\vee
y\vee \bar{u}\}$. Since $w$ is implied by $N(n,2,z)$, there is a
local fitness function $g = g(|x|, |y|, |u|)$ that implies $T_2$.
The conditional probability that $T_1$ is implied, is less than
or equal to $P_1+P_2$ where $P_1$ is the conditional probability
that $g$ also implies the clause $\bar{x}\vee y\vee \bar{u}$ given
that $g$ implies $T_2$, and $P_2$ is the conditional probability
that the clause $\bar{x}\vee y\vee \bar{u}$ is implied by other
local fitness functions. By the definition of $N(n,2,z)$, we have
that $P_1 = \frac{1}{6}\alpha$. Since a local fitness function
implies $\bar{x}\vee y\vee \bar{u}$ only if it has the same
variables with $g = g(|x|,|y|,|u|)$, we have that $P_2 =
O(\frac{1}{n})$. The claim is proved. It follows that, for
sufficiently large $n$,
\begin{equation}
\label{probabOneThmEQ03}
Pr\{\bar{w}\mid w\} \leq
     c\left(\frac{3+\sqrt{5}}{2}p_0\right)^{t-q}\cdot
        1^{q_1}\cdot \left(\frac{1}{6}\alpha\right)^{q_2}
\end{equation}
where $p_0$ is defined in Lemma \ref{3moduleLemma} and $c$ is a fixed constant.
\par
 Let $A_{Q,q,q_2}(w)$ be the set of t-3-modules that share $Q$ clauses
 with $w$ such that these $Q$ clauses are distributed over $q$
 different 3-modules. As before,  $q_1$ is the number of 3-modules
 whose two clauses are both shared and $q_2 = q-q_1$ the  number of
 3-modules that only has one clause shared. We claim that
\begin{equation}
\label{probabOneThmEQ04}
|A_{Q,q, q_2}(w)| = |A_{2q, q, 0}(w)|6^{q_2}.
\end{equation}
where $A_{2q, q, 0}(w)$ is the set of t-3-modules that share all
the $2q$ clauses in the $q$ 3-modules with $w$.
Let $\overline{M}=\{\overline{M_1}, \cdots , \overline{M_t}\}$
be a t-3-module in which all the clauses
$\overline{M_i}, 1\leq i\leq q$ are shared with $w$. Let
$M = \{M_1, \cdots , M_t\}$ be a t-3-module in which all
the clauses in $M_i, 1\leq i\leq q_1$ are shared and each
of the 3-modules $M_i, q_1 + 1\leq q_1+ q_2$ has only one
clause shared. Since for each of the $q_2$ 3-modules, we
have 6 ways to choose the non-shared clauses, there are
$6^{q_2}$ such t-3-modules $M$ in $A_{Q,q,q_2}(w)$ that
correspond to one t-3-module $\overline{M}$ in $A_{2q, q, 0}$.
The claims follow. From formula (55) and (56) in \cite{FRG98}
and (\ref{probabOneThmEQ04}), it follows that
\begin{equation}
\label{probabOneThmEQ05}
  |A_{Q, q, q_2}(w)| <
\begin{cases}
  \frac{O(t)}{n^2} 2^{t-q}n^{2(t-q)}6^{q_2}& ,q \leq p+1, \\
  \frac{O(1)}{n}2^{t-q}n^{2(t-q)}6^{q_2}& ,q > p+1.
\end{cases}
\end{equation}
Let $r = \left(\frac{1}{28}(1-\alpha) +
\frac{6}{56}\alpha\right)$, and write
$p_0 = \frac{1}{\binom{n-1}{2}}r$. Then, we have
\begin{equation}
\label{probabOneThmEQ06}
\begin{split}
 & |A_{Q,q,q_2}(w)|Pr\{\bar{w}\mid w\} \\
 &\leq \frac{O(t)}{n^2} 2^{t-q}n^{2(t-q)}6^{q_2}
          (\frac{3+\sqrt{5}}{2}p_0)^{t-q}
           (\frac{1}{6}\alpha)^{q_2} \\
 &\leq \frac{O(t)}{n^2} 2^{t-q}n^{2(t-q)}
         \left(\frac{3+\sqrt{5}}{2}r\right)^{t-q}
         \frac{1}{\binom{n-1}{2}^{t-q}} \\
 &\leq \frac{O(t)}{n} \frac{1}{4n} (2(3+\sqrt{5})r))^{t-q} \\
 &\leq \frac{O(t)}{n} E\{A_t\}(2(3+\sqrt{5})r))^{-q}, \ \ q \leq p+3
\end{split}
\end{equation}
and
\begin{equation}
\label{probabOneThmEQ07}
  |A_{Q,q,q_2}(w)|Pr\{\bar{w}\mid w\} \leq
     O(1)E\{A_t\}(2(3+\sqrt{5})r))^{-q}, \ \ q > p+3.
\end{equation}
Therefore,
\begin{equation}
\label{probabOneThmEQ08}
\begin{split}
 & \sum\limits_{\bar{w}\in A(w)}Pr(\bar{w}\mid w) =
    \sum\limits_{Q, q, q_2}|A_{Q,q, q_2}(w)|Pr\{\bar{w}\mid w\} \\
  &=\sum\limits_{Q=1}^{t}\sum\limits_{q \leq p+3}\sum\limits_{q_2}
       \frac{O(t)}{n} E\{A_t\}(2(3+\sqrt{5})r))^{-q} +
        \sum\limits_{Q=1}^{t}\sum\limits_{q >
                  p+3}\sum\limits_{q_2}
          O(1)E\{A_t\}(2(3+\sqrt{5})r))^{-q}.
\end{split}
\end{equation}
Since $2(3+\sqrt{5})r) > 1$ for $z > 2.837$, we have
\begin{equation}
\label{probabOneThmEQ09}
\begin{split}
  \sum\limits_{\bar{w}\in A(w)}Pr(\bar{w}\mid w)
    & \leq \frac{O(t^4)}{n}E\{A_t\} +
          t^3E\{A_t\}(4r)^{-(p+3)} \\
   &= o(E\{A_t\}).
\end{split}
\end{equation}
This completes the proof of Theorem \ref{probabOneThm}. \ \ \
$\qed$

\section{Experiments}
Our study of the threshold phenomena in NK landscapes started with
an experimental investigation. Many of the theoretical results in
the previous section are motivated by the observations made
in our experiments. In this section, we describe the approach and
methods we used in the experimental study, and report the
results and observations we have made.

In our experiments, an instance of the NK landscape decision problem
is converted to an equivalent 3-SAT problem, and then the 3-SAT
problem is solved using Roberto's relsat---an enhanced version of
the famous Davis-Putnam algorithm for SAT problems implemented  in
$C^{++}$. The source code of relsat can be found at
http://www.cs.ubc.ca/~hoos/SATLIB/.

In the experiments, we generated random instances of the NK
landscape decision problem from the random model $N(n,2,z)$. As a
result, the equivalent SAT problem for each random NK landscape
instance is a 3-SAT problem with $n$ variables and (on average)
$zn$ clauses. By definition, the parameter $z$ is between $0$ and
$8$. For $z\leq 1$, the 3-SAT instance can be solved easily by
setting the literals that correspond to the main variables of the
local fitness function to true. As $z$ increases, we get more and
more clauses and the 3-SAT problem becomes more and more
constrained. The aims of the experiments are
three-fold:(1)Investigating if there exists a threshold
phenomenon in the random NK landscape model; (2) Locating the
threshold of the parameter $z$; and (3)Determining if there are
any hard instances around the threshold.

\subsection{Experiments on the Fixed Ratio Model}
In this part of the experiments, we generate 100 random instances
of $N(n, 2, z)$ for each of the parameters $n = 2^9 \cdots 2^{16}$
and $z = 2.71, 2.72,\cdots , 3.00$. These instances are then
converted to 3-SAT instances and solved by {\sl relsat}. Figure 1
shows the fraction of insoluble instances as a function
of the parameter $z$. It can be seen that there exists a threshold
phenomenon and the threshold is around 2.83. This shows that our
upper bound $z = 2.837$ is very tight.
\begin{figure}[t]
\centerline{
   \psfig{figure=sat3Detail1.eps, height = 3in, width = 5in}
}
\begin{center}
\caption{Fractions of insoluble instances(Y-axis) as a
  function of $z$ (X-axis).}
\end{center}
\end{figure}

In Figure 2, we plot the square root of the average search cost
as a function of the parameter $n$. The figure  indicates that
the average search is in $O(n^2)$ for any parameter $z$. We have
also observed that more than 99 percent of the insoluble instances
are solved quickly in the preprocessing stage of relsat. This
indicates that there must be some ``small'' structures that make
the instances insoluble. More detailed experimental results can be
found in Gao's thesis \cite{GAO01}.

\begin{figure}[t]
\centerline{
   \psfig{figure=sat3Detail4.eps, height = 3in, width = 5in}
}
\caption{Square root of the average search cost (Y-axis, in seconds) as a
  function of $n$ (X-axis).}
\end{figure}


\subsection{Experiments on the 2-SAT sub-Problem}

\begin{figure}[t]
\centerline{
   \psfig{figure=sat2Final1.eps, height = 3in, width = 5in}
}
\caption{Fractions of insoluble instances(Y-axis) as a
  function of $z$ (X-axis) for 2-SAT sub-problems.}
\end{figure}


\begin{figure}[t]
\centerline{
   \psfig{figure=sat2Final4.eps, height = 3in, width = 5in}
}
\caption{Square root of the average search cost (Y-axis, in seconds) as a
  function of $n$ (X-axis) for 2-SAT sub-problems.}
\end{figure}


This is the part of the experiments that motivated our theoretical
analyses in Section \ref{2satSubsection}. The idea can be explained
as follows. Let
$$
  f(x) = \sum\limits_{i=1}^nf_i(x_i, \Pi (x_i))
$$
be an instance of the decision problem of NK landscape and
$$
    \varphi = C_1 \bigwedge C_2 \cdots \bigwedge C_n
$$
the equivalent 3-SAT problem where $C_i$ is the set of
3-clauses equivalent to the local fitness function $f_i$. For
each $i$, there is a set of 2-clauses $D_i$(possibly empty) implied
by $C_i$. For example, if $C_i$ has three 3-clauses
$((x, y, z), (x, \bar{y}, z), (x, y, \bar{z}))$, then the set
of 2-clauses $D_i$ would be $((x,z), (x,y))$.
The conjunction of $D_i$, denoted by $\bar{\varphi}$,
is a 2-SAT problem. It is obvious that the original
3-SAT problem $\varphi$ is satisfiable only if the 2-SAT
sub-problem $\bar{\varphi}$ is satisfiable. In the experiment,
we generate instances of the NK landscape $N(n, 2,z)$, convert
them to the equivalent 3-SAT problems, and extract
the 2-SAT sub-problems. These 2-SAT problems are then solved by
the relsat solver. If the 2-SAT problem is unsatisfiable, then the
original NK landscape instance is also insoluble.

The experimental settings are the same as those in the experiment
on the original problem. The results are shown in Figures 3-4, in
parallel to the Figures 1-2 of the results on the original 3-SAT
problems in Section 5.1. We see that the patterns of insoluble
fractions and search cost are similar to those we found in the
original 3-SAT problems. There is a soluble-insoluble phase
transition occurring around 2.83, but the fraction of
unsatisfiable instances is lower than the fraction in the
original 3-SAT problems.

 We also observed that the average search cost for the 2-SAT
 sub-problems remains the same as that for the original 3-SAT
 problems. This tells us that the difficulty of solving a soluble
 instance of NK landscape is almost the same as that of solving a
 2-SAT problem, and hence is easy. Therefore, on average the
 NK landscape $N(n,2,z)$ is also easy at parameters below the
 threshold where almost all of the instances are soluble.

\section{Implications and Conclusions}
One of the questions that arises about this work is its
implications to the design and analysis of genetic algorithms. NK
landscapes were initially conceived as simplified models of
evolutionary landscapes which could be tuned with respect to
ruggedness and epistatic interactions \cite{KAU89}. In the study
of genetic algorithms, NK landscape models have been used as a
prototype and benchmark in the analysis of the performance of
different genetic operators and the effects of different encoding
methods on the algorithm's performance \cite{ALT96,HOR97,JON95}.
\citeA{kauf93} points out that the parameters that primarily
affect a number of ruggedness measures are $n$ and $k$.

Nevertheless, the fact that for $k \ge 2$ the discrete NK
landscape is NP-complete \cite {WTZ99} when the neighbors are
arbitrarily chosen could be construed as implying that random
landscapes with fixed $k$ are in practice hard.

The results in this paper should serve as a cautionary note that
this may not be the case.  Our analyses show that for fixed $k$
the uniform probability model is trivially solvable as the problem
size tends to infinity. For the fixed ratio model, we have derived
two upper bounds for the threshold of the solubility phase transition,
and proved that the problem with the control parameter above the
upper bounds can be solved in polynomial time with probability
asymptotic to 1 due to the existence of easy sub-problems such
as 2-SAT. A series of experiments has also been conducted to investigate
the hardness of the problem with the control parameters around and
below the threshold. From the experiments, we have observed that
the  problem is also easy around and below the threshold.

Our proofs hold only for the decision version of the problem where
the component functions are discrete on $\{0,1\}$. The proofs are
obtained by noticing that the clustering of functions, or clauses,
on selected subsets of variables implies that the overall problem
is decomposable into independent subproblems, or that the problem
contains small substructures that identify the solution.
The subproblems are the components of the connection graph defined
in Section \ref{uniformModel} and the 2-SAT sub-problems studied
in Section \ref{2satSubsection}.  It is currently unclear to us
to what extent our analysis can be extended to the optimization
version of the NK model, and we would like to study
this problem further in the future.

In response to the question `what are the implications for GAs?'
we suggest the following speculative line of enquiry. For the
discrete model we use, the soluble instances are readily solved
by a standard algorithmic approach based on recognizing the
components of the connection graph. (This should not be a surprise
for us as it has been pointed out by \citeA{HRM99} that  `Even
relatively old algorithms such as Davis-Putnam which are deterministic
and exact are orders of magnitude faster than GAs'.)
\footnote{  We thanks an anonymous referee for pointing out to us the
            work of Heckendorn, et al. \cite{HRM99}}
A similar connectivity can be
developed for real valued distributions, for example by capping
the minimum value which we allow a sub-function to take. We can
speculate that the clustering imposed by fixed values of $k$
would also generate localized structures when real values are
applied and when considering optimization instead of decision,
but perhaps with fuzzy boundaries. In fact, this observation is
just the flip side of limited epistasis. Genetic algorithms, or
their variants such as the probabilistic model-building
algorithms \cite{LAR01}, designed to mimic natural evolution, are
supposed to take
advantage of this situation. So, to the extent that NK landscapes
are an accurate reflection of the features exploited by
evolutionary algorithms, we pose the following question. Is it
possible to identify these fuzzy components if they exist, and in
doing so design an algorithm that exploits the same landscape
features that the evolutionary algorithms do, but far more
efficiently, as we have done for the uniform discrete decision
problem?

These landscapes were designed with the intent of studying limited
interactions, and our results can also be seen as a confirmation that
indeed limited epistasis leads to easier problems.
In another domain, that of the more traditional research into search
and optimization, there is a need for test bed problems with real world
connections which are tunable with respect to difficulty.  NK landscapes
might have been such a domain for generating 3-SAT instances. It is
disappointing that for restricted $k$ the instances generated are easy
with high probability.

\acks{This research supported in part by Natural Sciences and
Engineering Research Council Grant No. OGP8053. We thank the
anonymous reviewers for their comments.}

\bibliography{nkbib}
\bibliographystyle{theapa}

\end{document}
