RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2009 Volume 21, Issue 1, Pages 139–157 (Mi dm1043)

This article is cited in 8 papers

New upper bounds for the problem of maximal satisfiability

A. S. Kulikov, K. Kutskov


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.

UDC: 519.7

Received: 11.03.2008

DOI: 10.4213/dm1043


 English version:
Discrete Mathematics and Applications, 2009, 19:2, 155–172

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025