期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Recently there was an explosion in proving
(exponential-time) worst-case upper bounds
for the propositional satisfiability problem (SAT)
and related problems, mainly, k-SAT, MAX-SAT and
MAX-2-SAT. The previous version of this paper
contained an algorithm for MAX-2-SAT,
and a "proof" of the theorem stating that
this algorithm runs in time of the order 2^{K_2/4},
where K_2 is the number of 2-clauses in the input
formula. This bound and the corresponding bound
2^{L/8} (where L is the length of the input formula)
are still the best known. However, Jens Gramm
pointed out to the author that the algorithm
in the previous revision of this paper had an error.
In this revision of the paper, we present
a corrected version of the algorithm and
the proof of the same upper bound.
The proof is still based on the key idea
to count only 2-clauses (and not 1-clauses).
However, the use of Yannakakis' symmetric flow algorithm
is replaced by several transformation rules.
关键词：Algorithms for NP-complete problems, MAX-SAT, propositional satisfiability, worst-case upper bounds
