Search

The satisfiability of a given branching program is to determine whether there exists a consistent path from the root to 1-sink. In a syntactic read-k-times branching program, each variable appears at most k times in any path from the root to a sink. In a preliminary version of this paper, we provide a satisfiability algorithm for syntactic read-k-times branching programs with n variables and m edges that runs in time O poly (n , m k 2 ) ⋅ 2 (1 − 4 − k − 1) n . In this paper, we improve the bounds for k = 2. More precisely, we show that the satisfiability of syntactic read-twice branching programs can be solved in time O poly (n , m) ⋅ 2 5 n / 6 . Our algorithm is based on the decomposition technique shown by Borodin, Razborov and Smolensky [Computational Complexity, 1993]. [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]