2012 | OriginalPaper | Chapter
Efficient Arbitrary and Resolution Proofs of Unsatisfiability for Restricted Tree-Width
Author : Martin Fürer
Published in: LATIN 2012: Theoretical Informatics
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We consider unsatisfiable Boolean formulas in conjunctive normal form. It is known that unsatisfiability can be shown by a regular resolution proof in time polynomial in the number of variables
n
, and exponential in the tree-width
w
. It is also known that satisfiability for bounded tree-width can actually be decided in time linear in the length of the formula and exponential in the tree-width
w
.
We investigate the complexities of resolution proofs and arbitrary proofs in more detail depending on the number of variables
n
and the tree-width
w
. We present two very traditional algorithms, one based on resolution and the other based on truth tables. Maybe surprisingly, we point out that the two algorithms turn out to be basically the same algorithm with different interpretations.
Similar results holds for a bound
w
′ on the tree-width of the incidence graph for a somewhat extended notion of a resolution proof. The length of any proper resolution proof might be quadratic in
n
, but if we allow to introduce abbreviations for frequently occurring subclauses, then the proof length and running time are again linear in
n
.