1. A Moderately Exponential Time Algorithm for k-IBDD Satisfiability.
- Author
-
Nagao, Atsuki, Seto, Kazuhisa, and Teruyama, Junichi
- Subjects
- *
SATISFIABILITY (Computer science) , *BINARY number system , *ALGORITHMS , *MATHEMATICAL equivalence , *POLYNOMIALS - Abstract
We present a satisfiability algorithm for k-indexed binary decision diagrams (k-IBDDs). The proposed exponential space and deterministic algorithm solves the satisfiability of k-IBDDs, i.e., k-IBDD SAT, for instances with n variables and cn nodes in O2(1-μk(c))n
time, where μk(c)=Ω1(k22klogc)2k-1-1 . We also provide a polynomial space and deterministic algorithm that solves a k-IBDD SAT of polynomial size for any constant k≥2 in O2n-n1/2k-1 time. In addition, the proposed algorithm is applicable to equivalence checking of two IBDDs. [ABSTRACT FROM AUTHOR] - Published
- 2018
- Full Text
- View/download PDF