## The Computational Complexity of N-K Fitness Functions

posted 10/15/99
The Computational Complexity of N-K Fitness Functions
Alden H. Wright
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812
wright@cs.umt.edu
(406) 243-4790
http://www.cs.umt.edu/u/wright/wright.htm
Abstract
The N-K fitness landscapes have been widely used as examples
and test functions in the field of evolutionary computation.
Thus, the computational complexity of these landscapes as
optimization problems is of interest. We investigate the
computational complexity of the problem of optimizing the
N-K fitness functions and related fitness functions.
We give an algorithm to optimize adjacent-model N-K fitness
functions which is polynomial in $N$. We show that the
decision problem corresponding to optimizing random-model
N-K fitness functions is NP-complete for $K > 1$ and is
polynomial for $K = 1$. However, if the restriction that
the $i$th component function depends on the $i$th bit is
removed, then the problem is NP-complete even for $K=1$.
We also give a polynomial-time approximation algorithm
for the arbitrary-model N-K optimization problem.