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

Bolette Ammitzbøll Madsen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

An 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?

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research