RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 1997 Volume 241, Pages 30–71 (Mi znsl481)

This article is cited 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.

UDC: 519.5

Received: 19.04.1997


 English version:
Journal of Mathematical Sciences (New York), 2000, 98:4, 442–463

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024