1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University
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?
Information Processing Letters, 2006, Vol 97, Issue 1, p. 28-30