Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-010 | 12th January 2000 00:00

Supermodels and Closed Sets


Authors: Amitabha Roy, Christopher Wilson
Publication: 22nd February 2000 09:39
Downloads: 1454


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

ISSN 1433-8092 | Imprint