## 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.