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 |

Last modified: 2004-10-13 by webmaster.