Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR99-036 | 12th February 2000 00:00

A 2^{K/4}-time Algorithm for MAX-2-SAT: Corrected Version Revision of: TR99-036

RSS-Feed




Revision #2
Authors: Edward Hirsch
Accepted on: 12th February 2000 00:00
Downloads: 4019
Keywords: 


Abstract:

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.


Revision #1 to TR99-036 | 2nd October 1999 00:00

A New Algorithm for MAX-2-SAT Revision of: TR99-036





Revision #1
Authors: Edward Hirsch
Accepted on: 2nd October 1999 00:00
Downloads: 4035
Keywords: 


Abstract:

Recently there was a significant progress in
proving (exponential-time) worst-case upper bounds for the
propositional satisfiability problem (SAT).
MAX-SAT is an important generalization of SAT.
Several upper bounds were obtained for MAX-SAT and
its NP-complete subproblems.
In particular, Niedermeier and Rossmanith recently
proved the worst-case upper bound O(2^{K/2.88...}) for
MAX-2-SAT (i.e. each clause contains at most two variables),
where K is the number of clauses,
In this paper we improve this bound to O(2^{k/4}),
where k is the number of 2-clauses.
In addition, our algorithm and the proof are much simpler
than those of Niedermeier and Rossmanith.
The key ideas are to use the symmetric flow algorithm of
Yannakakis and to count only 2-clauses (and not 1-clauses).


Paper:

TR99-036 | 6th September 1999 00:00

A New Algorithm for MAX-2-SAT





TR99-036
Authors: Edward Hirsch
Publication: 15th September 1999 17:16
Downloads: 4651
Keywords: 


Abstract:

Recently there was a significant progress in
proving (exponential-time) worst-case upper bounds for the
propositional satisfiability problem (SAT).
MAX-SAT is an important generalization of SAT.
Several upper bounds were obtained for MAX-SAT and
its NP-complete subproblems.
In particular, Niedermeier and Rossmanith recently
proved the worst-case upper bound O(2^{K/2.88...}) for
MAX-2-SAT (i.e. each clause contains at most two variables),
where K is the number of clauses.
In this paper we improve this bound to O(2^{k/4}),
where k is the number of 2-clauses.
In addition, our algorithm and the proof are much simpler
than those of Niedermeier and Rossmanith.
The key ideas are to use the symmetric flow algorithm of
Yannakakis and to count only 2-clauses (and not 1-clauses).



ISSN 1433-8092 | Imprint