期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
