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 , where is the number of clauses and is the length of the formula. Skjernaa has given an algorithm for Exact Satisfiability with time bound 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 , where is a constant and is the number of clauses?

Available as PostScript, PDF, DVI.