Search

This paper studies the average complexity on the number of comparisons for sorting algorithms. Its information-theoretic lower bound is n lg ⁡ n − 1.4427 n + O (log ⁡ n). For many efficient algorithms, the first n lg ⁡ n term is easy to achieve and our focus is on the (negative) constant factor of the linear term. The current best value is −1.3999 for the MergeInsertion sort. Our new value is −1.4106, narrowing the gap by some 25%. An important building block of our algorithm is "two-element insertion," which inserts two elements A and B , A < B , into a sorted sequence T. This insertion algorithm is still sufficiently simple for rigorous mathematical analysis and works well for a certain range of the length of T for which the simple binary insertion does not, thus allowing us to take a complementary approach together with the binary insertion. [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]