TY - GEN
T1 - Efficient arbitrary and resolution proofs of unsatisfiability for restricted tree-width
AU - Fürer, Martin
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84860818217&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84860818217&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-29344-3_33
DO - 10.1007/978-3-642-29344-3_33
M3 - Conference contribution
AN - SCOPUS:84860818217
SN - 9783642293436
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 387
EP - 398
BT - LATIN 2012
T2 - 10th Latin American Symposiumon Theoretical Informatics, LATIN 2012
Y2 - 16 April 2012 through 20 April 2012
ER -