Does SAT exhibit fractal behavior?
Joost J. Joosten, Grant Olney Passmore
Abstract:
In this paper we study the structure of the set SAT of
all satisfiable propositional logical formulas. In particular
we raise the question whether the distribution
of SAT within the set A of all propositional formulas
exhibits fractal behavior. This answer is of course
relative to a metric on A. We show that for one such
metric there is strong evidence that the distribution
does indeed behave wildly. Next we look at an alternative
metric.