Additively Decomposable Fitness Functions Abstract

Richard K. Thompson     & Alden H. Wright
rkt@charlo.math.umt.edu & wright@cs.umt.edu

Computer Science Dept.
The University of Montana
Missoula, MT 59812-1008

ABSTRACT
We define a class of optimization objective functions over discrete
domains called additively decomposable functions.  An 
additively decomposable function is a function over several discrete
variables that can be written as a sum of component functions, each
of which depends on only a small number of those variables.  The 
$N\!K$ fitness landscapes defined by Kauffman are a special case.
If the domain variables have a circular ordering, then under
the adjacent model, we impose the further restriction that
each component function depends on a sequence of adjacent variables
in the ordering.  Bandwidth-constrained problems and adjacent $N\!K$
landscapes are special cases.  We give a polynomial-complexity dynamic 
programming algorithm to optimize adjacent-model additively decomposable 
functions, and show that without the adjacency assumption, the 
optimization problem is NP-complete.