On the Negation-Limited Circuit Complexity of Sorting and Inverting k-tonic Sequences

摘要

A binary sequence x_1,...,x_n is called k-tonic if it contains at most k changes between 0 and 1, i.e., there are at most k indices such that x_i ≠ x_i+1. A sequence -x_1,..., -x_n is called an inversion of x_1,... ,x_n. In this paper, we investigate the size of a negation-limited circuit, which is a Boolean circuit with a limited number of NOT gates, that sorts or inverts k-tonic input sequences. We show that if k = O(1) and t = O (log log n), a k-tonic sequence of length n can be sorted by a circuit with t NOT gates whose size is O((n log n)/2~(ct)) where c > 0 is some constant. This generalizes a similar upper bound for merging by Amano, Maruoka and Tarui, which corresponds to the case k = 2. We also show that a k-tonic sequence of length n can be inverted by a circuit with O(k log n) NOT gates whose size is O(kn) and depth is O(k log~2 n). This reduces the size of the negation-limited inverter of size O(n log n) by Beals, Nishino and Tanaka when k = o(log n). If k = O(1), our inverter has size O(n) and depth O(log~2 n) and contains O(log n) NOT gates. For this case, the size and the number of NOT gates are optimal up to a constant factor.