Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419912 | Discrete Applied Mathematics | 2008 | 13 Pages |
Abstract
We prove that binary decision diagrams [R. Bryant, Symbolic Boolean manipulation with ordered binary decision diagrams, ACM Comput. Surveys 23 (3) (1992)] can be polynomially simulated by the extended resolution rule of [G.S. Tseitin, On the complexity of derivation in propositional calculus, in: A. Slisenko (Ed.), Studies in Constructive Mathematics and Mathematical Logics, 1968]. More precisely, for any unsatisfiable formula φφ, there exists an extended resolution refutation of φφ where the number of steps is polynomially bounded by the maximal size of the BDDs built from the formulae occurring in φφ.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nicolas Peltier,