ECCC-Report TR00-010https://eccc.weizmann.ac.il/report/2000/010Comments and Revisions published for TR00-010en-usTue, 22 Feb 2000 09:39:28 +0200
Paper TR00-010
| Supermodels and Closed Sets |
Amitabha Roy,
Christopher Wilson
https://eccc.weizmann.ac.il/report/2000/010 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$.
Tue, 22 Feb 2000 09:39:28 +0200https://eccc.weizmann.ac.il/report/2000/010