The computational complexity of N-K fitness functions
N-K fitness landscapes have been used widely 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. If the restriction that the ith component function depends on the ith 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.
computational complexity n-k fitness function optimization