###
Petersburg Department of Steklov Institute of Mathematics

#
PREPRINT 4/1997

Edward A. Hirsch
###
Deciding satisfiability of formulas with *K* clauses
in less than 2^{0.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
2^{K/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 2^{0.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