|
This article is cited in 7 scientific papers (total in 7 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.
Received: 11.03.2008
Citation:
A. S. Kulikov, K. Kutskov, “New upper bounds for the problem of maximal satisfiability”, Diskr. Mat., 21:1 (2009), 139–157; Discrete Math. Appl., 19:2 (2009), 155–172
Linking options:
https://www.mathnet.ru/eng/dm1043https://doi.org/10.4213/dm1043 https://www.mathnet.ru/eng/dm/v21/i1/p139
|
Statistics & downloads: |
Abstract page: | 547 | Full-text PDF : | 229 | References: | 45 | First page: | 13 |
|