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.