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