New upper bounds for the problem of maximal satisfiability

Published by De Gruyter May 28, 2009

Showing a limited preview of this publication:

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.

Received: 2008-03-11

Published Online: 2009-05-28

Published in Print: 2009-May