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 x(1),...,x(n) and outputs -x(1),....,-x(n), 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(n log n), depth O(log n), and [log(2)(n + 1)] NOTs. A zero-one sequence x(1),....,x(n) is k-tonic if the number of is such that x(i) not equal x(i+1) is at most k. The notion generalizes well-known bitonic sequences. We give a construction of circuits inverting k-tonic sequences with size O((log k) n) and depth O(log k log log n + log n) using 1092 n+ 10921092 log(2) n +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 10921092 n + 109210921092 n + O(1) NOT gates for the case where k = O(1). The following question by Turan remains open: Is the size of any depth-O(log n) inverter with O(log n) NOT gates superlinear? (C) 2008 Elsevier B.V. All rights reserved.
inverter k-tonic circuit complexity negation-limited circuit