Petersburg Department of Steklov Institute of Mathematics
PREPRINT 4/1997
Edward A. Hirsch
Deciding satisfiability of formulas with K clauses
in less than 20.30897K steps
This preprint was accepted January, 1997.
Contact: E.A.Hirsch
Abstract:
In 1980 B. Monien and E. Speckenmeyer proved the worst-case upper bound
2K/3 on the time complexity of the propositional satisfiability
problem, where K is the number of clauses in the input formula.
The present paper improves this bound to 20.30897K by using
a new method, called the extended sign principle.
[ Full text:
(
.ps.gz)
]
Back to preprints of this year (1997)
Back to all preprints
Back to the Petersburg Department of
Steklov Institute of Mathematics