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]

Abstract: The counterfeit coin problem requires us to find all false coins from a given bunch of coins using a balance scale. We assume that the balance scale gives us only “balanced” or “tilted” information and that we know the number of false coins in advance. The balance scale can be modeled by a certain type of oracle and its query complexity is a measure for the cost of weighing algorithms (the number of weighings). In this paper, we study the quantum query complexity for this problem. Let be the quantum query complexity of finding all false coins from the given coins. We show that for any and such that , , contrasting with the classical query complexity, , that depends on . So our quantum algorithm achieves a quartic speed-up for this problem. We do not have a matching lower bound, but we show some evidence that the upper bound is tight: any algorithm, including our algorithm, that satisfies certain properties needs queries. [Copyright &y& Elsevier]