Search

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]

We present improved exponential time exact algorithms for Max SAT. Our algorithms run in time of the form O ( 2 ( 1 − μ ( c ) ) n ) for instances with n variables and m = c n clauses. In this setting, there are three incomparable currently best algorithms: a deterministic exponential space algorithm with μ ( c ) = 1 O ( c log ⁡ c ) due to Dantsin and Wolpert (2006) [9] , a randomized polynomial space algorithm with μ ( c ) = 1 O ( c log 3 ⁡ c ) and a deterministic polynomial space algorithm with μ ( c ) = 1 O ( c 2 log 2 ⁡ c ) due to Sakai, Seto and Tamaki (2015) [30] . Our first result is a deterministic polynomial space algorithm with μ ( c ) = 1 O ( c log ⁡ c ) that achieves the previous best time complexity without exponential space or randomization. Furthermore, this algorithm can handle instances with exponentially large weights and hard constraints. The previous algorithms and our deterministic polynomial space algorithm run super-polynomially faster than 2 n only if m = O ( n 2 ) . Our second results are deterministic exponential space algorithms for Max SAT with μ ( c ) = 1 O ( ( c log ⁡ c ) 2 / 3 ) and for Max 3-SAT with μ ( c ) = 1 O ( c 1 / 2 ) that run super-polynomially faster than 2 n when m = o ( n 5 / 2 / log 5 / 2 ⁡ n ) and m = o ( n 3 / log 2 ⁡ n ) respectively. Our third result is a randomized exponential space algorithm for Max SAT with μ ( c ) = 1 O ( c 1 / 2 log 3 / 2 ⁡ c ) that run super-polynomially faster than 2 n when m = o ( n 3 / log 5 ⁡ n ) . [ABSTRACT FROM AUTHOR]