Covers: A Theory of Boolean Function Decomposition
Scott E. Page
Division of Humanities and Social Sciences 228-77,
California Institute of Technology, Pasadena, CA 91125, USA
Abstract
In this paper, we develop a theory of covers for functions defined over boolean strings. Given a function, a cover is a decomposition, though not necessarily a partition, of the bits into subproblems that can be solved in parallel. In the paper, we formulate the notion of cover size, which equals the size of the largest subproblem in a decomposition for a particular function. Cover size is defined relative to a function's upper contour sets. An implication of cover theory is that a problem's difficulty, as measured by its cover size, necessarily decreases as the function value improves. We also show how cover theory lends insight to the performance of hillclimbing algorithms and genetic algorithms, and present data from simulations that support a covers-based explanation for genetic algorithm performance.
