Search

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]