Linear-size log-depth negation-limited inverter for k-tonic binary sequences

In negation-limited complexity, one considers circuits with a limited number of NOT gates, being motivated by the gap in our understanding of monotone versus general circuit complexity. In this context, the study of inverters, i.e., circuits with inputs x1,…,xn and outputs ¬x1,…,¬xn, is fundamental since an inverter with r NOTs can be used to convert a general circuit to one with only r NOTs. Beals, Nishino, and Tanaka [R. Beals, T. Nishino, K. Tanaka, On the complexity of negation-limited Boolean networks, SIAM Journal on Computing 27 (5) (1998) 1334–1347. A preliminary version appears in: Proceedings of STOC95: The 27th Annual ACM Symposium on Theory of Computing, 1995, pp. 585–595] gave a construction of an n-inverter with size O(nlogn), depth O(logn), and ⌈log2(n+1)⌉ NOTs. A zero–one sequence x1,…,xn is k-tonic if the number of i’s such that xi≠xi+1 is at most k. The notion generalizes well-known bitonic sequences. We give a construction of circuits inverting k-tonic sequences with size and depth using log2n+log2log2log2n+O(1) NOTs. In particular, for the case where k=O(1), our k-tonic inverter achieves asymptotically optimal linear size and logarithmic depth. Our construction improves all the parameters of the k-tonic inverter by Sato, Amano, and Maruoka [T. Sato, K. Amano, A. Maruoka, On the negation-limited circuit complexity of sorting and inverting k-tonic sequences, in: Proceedings of COCOON06: The 12th Annual International Computing and Combinatorics Conference, in: Lecture Notes in Computer Science, vol. 4112, 2006, pp. 104–115]. We also give a construction of k-tonic sorters achieving linear size and logarithmic depth with log2log2n+log2log2log2n+O(1) NOT gates for the case where k=O(1). The following question by Turán remains open: Is the size of any depth-O(logn) inverter with O(logn) NOT gates superlinear?