期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：In this paper we study the approximability of boolean constraint
satisfaction problems. A problem in this class consists of some
collection of ``constraints'' (i.e., functions
f:01k01 ); an instance of a problem is a set
of constraints applied to specified subsets of n boolean
variables. Schaefer earlier studied the question of whether one
could find in polynomial time a setting of the variables satisfying
all constraints; he showed that every such problem is either in P
or is NP-complete. We consider optimization variants of these
problems in which one either tries to maximize the number of
satisfied constraints (as in MAX 3SAT or MAX CUT) or tries to
find an assignment satisfying all constraints which maximizes the
number of variables set to 1 (as in MAX CUT or MAX CLIQUE). We
completely classify the approximability of all such problems.
In the first case, we show that any such optimization problem
is either in P or is MAX SNP-hard. In the second case, we
show that such problems fall precisely into one of five classes:
solvable in polynomial-time, approximable to within constant factors
in polynomial time (but no better), approximable to within polynomial
factors in polynomial time (but no better), not approximable to within
any factor but decidable in polynomial time, and not decidable in
polynomial time (unless P = NP). This result proves formally for this
class of problems two results which to this point have only
been empirical observations; namely, that NP-hard problems in
MAX SNP always turn out to be MAX SNP-hard, and that there seem
to be no natural maximization problems approximable to within
polylogarithmic factors but no better.
