Abstract:
A {\em supermodel} is a satisfying assignment of a boolean formula for which any small alteration, such as a single bit flip, can be repaired by another small alteration, yielding a nearby satisfying assignment. We study computational problems associated with super models and some generalizations thereof. For general formulas, it is NP-complete to determine if it has a supermodel. We examine 2-SAT and HORNSAT, both of which have polynomial time satisfiability tests. We see that while 2-SAT has a polynomial time test for a supermodel, testing whether a HORNSAT formula has one is NP-complete. We then look at sets of supermodels called {\em closed sets} - these are sets of supermodels which retain the supermodel property even after being broken and repaired. Using combinatorial methods, we examine extremal properties of closed sets. We find that they are at least linear in size. For large ones, an upper bound is trivial, but we see that the largest {\em minimal} closed set has size between $2^{2n/3}$ and $(4/5)2^{n-1}$. A {\em sparse} closed set is one in which each break of a supermodel has only a single repair. We obtain analogous, and slightly tighter, bounds on sparse closed sets, whose sizes essentially must lie between $(2e)^{n/8}$ and $2^n/n$.