### Abstract

In 1980 B. Monien and E. Speckenmeyer proved that satisfiability of a propositional formula consisting of K clauses can be checked in time of the order 2^{K/3}. Recently O. Kullmann and H. Luckhardt proved the bound 2^{L/9}, where L is the length of the input formula. The algorithms leading to these bounds (like many other SAT algorithms) are based on splitting, i.e., they reduce SAT for a formula F to SAT for several simpler formulas F_{1}, F_{2}, ..., F_{m}. These algorithms simplify each of F_{1}, F_{2}, ..., F_{m} according to some transformation rules such as the elimination of pure literals, the unit propagation rule etc. In this paper we present a new transformation rule and two algorithms using this rule. These algorithms have the bounds 2^{0.30897 K} and 2^{0.10537 L} respectively.

Original language | English |
---|---|

Pages | 521-530 |

Number of pages | 10 |

Publication status | Published - 1 Dec 1998 |

Event | Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA Duration: 25 Jan 1998 → 27 Jan 1998 |

### Conference

Conference | Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms |
---|---|

City | San Francisco, CA, USA |

Period | 25/01/98 → 27/01/98 |

### Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Two new upper bounds for SAT'. Together they form a unique fingerprint.

## Cite this

*Two new upper bounds for SAT*. 521-530. Paper presented at Proceedings of the 1998 9th Annual ACM SIAM Symposium on Discrete Algorithms, San Francisco, CA, USA, .