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

Bolette Ammitzbøll Madsen

September 2004

Abstract:

We give an algorithm for Exact Satisfiability with polynomial space usage and a time bound of $poly(L) \cdot 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) \cdot 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?

Available as PostScript, PDF, DVI.

Last modified: 2004-10-13 by webmaster.