Open AccessAn Algorithm for Exact Satisfiability Analysed with the Number of Clauses as Parameter
Author(s) -
Bolette Ammitzbøll Madsen
Publication year - 2004
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v11i18.21843
Subject(s) - satisfiability , mathematics , pspace , combinatorics , constant (computer programming) , discrete mathematics , time complexity , upper and lower bounds , exponential function , exact solutions in general relativity , boolean satisfiability problem , polynomial , space (punctuation) , algorithm , computational complexity theory , computer science , mathematical analysis , programming language , operating system
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?