TR00-010 Authors: Amitabha Roy, Christopher Wilson

Publication: 22nd February 2000 09:39

Downloads: 1197

Keywords:

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