Abstract:
In this paper we present relatively simple proofs of the following new upper bounds:
$c^N$, where $c<2$ is a constant and $N$ is the number of variables, for MAX-SAT for formulas with constant clause density;
$2^{K/6}$, where $K$ is the number of clauses, for MAX-2-SAT;
$2^{N/6,7}$ for $(n,3)$-MAX-2-SAT.
All bounds are proved by the splitting method. The main two techniques are combined complexity measures and clause learning.