An Algorithm for Exact Satisfiability Analysed with the Number of Clauses as Parameter

Authors

  • Bolette Ammitzbøll Madsen

DOI:

https://doi.org/10.7146/brics.v11i18.21843

Abstract

We give an algorithm for Exact Satisfiability with polynomial space usage and a time bound of poly(L) . m!, where m is the number of clauses and L is the length of the formula. Skjernaa has given an algorithm for Exact Satisfiability with time bound poly(L) . 2^m but using exponential space. We leave the following problem open: Is there an algorithm for Exact Satisfiability using only polynomial space with a time bound of c^m, where c is a constant and m is the number of clauses?

Downloads

Published

2004-09-11

How to Cite

Madsen, B. A. (2004). An Algorithm for Exact Satisfiability Analysed with the Number of Clauses as Parameter. BRICS Report Series, 11(18). https://doi.org/10.7146/brics.v11i18.21843