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.

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).

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).