|
Zapiski Nauchnykh Seminarov POMI, 1997, Volume 241, Pages 30–71
(Mi znsl481)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
Separating sings in the propositional satisfiability problem
E. A. Hirsch St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences
Abstract:
In 1980 B. Monien and E. Speckenmeyer, and (independently) Dantsin, proved that satisfiability of a propositional formula in CNF can be checked in less than $2^N$ steps ($N$ is the number of variables).
Later many other upper bounds for SAT and its subproblems we proved. A formula in CNF is in CNF-($1,\infty$), if each positive literal occurs in it at most once. H. Luckhardt in 1984 studied formulas in
CNF-($1,\infty$). In this paper we prove several new upper bounds for formulas in CNF-($1,\infty$) by introducing new signs separation principle. Namely, we present algorithms working the time of the order $1.1939^K$ and $1.0644^L$ for a formula consisting of $K$ clauses containing $L$ literals occurences. We also present an algorithm for formulas in CNF-($1,\infty$) whose clauses are bounded in length.
Received: 19.04.1997
Citation:
E. A. Hirsch, “Separating sings in the propositional satisfiability problem”, Studies in constructive mathematics and mathematical logic. Part X, Zap. Nauchn. Sem. POMI, 241, POMI, St. Petersburg, 1997, 30–71; J. Math. Sci. (New York), 98:4 (2000), 442–463
Linking options:
https://www.mathnet.ru/eng/znsl481 https://www.mathnet.ru/eng/znsl/v241/p30
|
Statistics & downloads: |
Abstract page: | 199 | Full-text PDF : | 61 |
|