Optimal length tree-like resolution refutations for 2SAT formulas
Author:
Open Access
- 1 April 2004
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 5 (2) , 316-320
Abstract
In this article, we exploit the graphical structure of 2SAT formulas to show that the shortest tree-like resolution refutation of an unsatisfiable 2SAT formula can be determined in polynomial time.Keywords
This publication has 13 references indexed in Scilit:
- Simplified and improved resolution lower bounds2002
- Intractability of read-once resolution2002
- Short proofs are narrow—resolution made simpleJournal of the ACM, 2001
- Combining Logic and Optimization in Cutting Plane TheoryLecture Notes in Computer Science, 2000
- Lower bounds for resolution and cutting plane proofs and monotone computationsThe Journal of Symbolic Logic, 1997
- Complexity of finding short resolution proofs1997
- Real-Time Database and Information Systems: Research Advances1997
- The Complexity of Propositional ProofsThe Bulletin of Symbolic Logic, 1995
- The intractability of resolutionTheoretical Computer Science, 1985
- A linear-time algorithm for testing the truth of certain quantified boolean formulasInformation Processing Letters, 1979