Abstract
The decrease of a Boolean function f : {0,1}n →{0,1}, denoted by d(f) is the maximum number of inverse indices in any increasing chain of inputs \(x_1, \ldots ,x_\ell \in \{0,1\}^n\), where i is an inverse index if f(x i ) > f(x i + 1). It follows from a theorem of Markov (JACM 1958) that the minimum number of negation gates in a circuit necessary and sufficient to compute any Boolean function f is ⌈log(d(f) + 1) ⌉. A recent result due to Morizumi (ICALP 2009) proves that d(f) negations are necessary and sufficient when the computation is done by formulas. We explore the situation in between formulas (directed trees) and general circuits (DAGs), and related models. We obtain the following results:
-
1
We argue that for any Boolean function f, there is a circuit computing f, that uses ⌈log(d(f) + 1) ⌉ negations and has treewidth at most ⌈log(d(f) + 1)⌉ + 1. For 1 ≤ k ≤ ⌈log(d(f) + 1) ⌉, we prove that d(f)·8k/2k negations are sufficient to compute any Boolean function f by circuits of treewidth at most k. Moreover, if there is a circuit family of size s = s(n) and treewidth k = k(n) computing {f n }, then there exists a circuit family of size s·n O(1)·2O( min {k,logn}) and treewidth at most 2k which computes {f n } and contains O( max {nk/22k,logn}) negation gates.
-
1
We obtain tight bounds on the number of negation gates required to compute specific functions such as \(\textsc{Parity}_{n},\overline{\textsc{Parity}_{n}}\) and \(\textsc{Inverter}_n\) by one-input-face upward planar circuits. We extend these lower bounds to a larger class of functions (which also includes natural functions like Add and Subtract) and we show a direct sum theorem for this class with respect to the number of negations.
-
1
We demonstrate the limitations of the one-input-face constraint in the upward planar circuits by showing the explicit function which can be computed by a monotone upward planar circuit, but cannot be computed by any montone one-input-face upward planar circuit.
-
1
We prove that for every Boolean function f, there exists a multilective upward planar circuit which uses at most \(\lceil \frac{d(f)+1}{2}\rceil\) negation gates for computing f.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Amano, K., Maruoka, A.: A superpolynomial lower bound for a circuit computing the clique function with at most (1/6)log log n negation gates. SIAM Journal of Computing 35(1), 201–216 (2005)
Barrington, D.A.M., Lu, C.-J., Miltersen, P.B., Skyum, S.: On Monotone Planar Circuits. In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity (CCC), pp. 24–31 (1999)
Beynon, M., Buckle, J.: On the planar monotone computation of boolean functions. Theor. Comput. Sci. 53(2-3), 267–279 (1987)
Fischer, M.: The complexity of negation-limited networks (a brief survey). LNCS, vol. 33, pp. 71–82. Springer, Heidelberg (1974)
Jansen, M., Sarma, M.N., Jayalal: Balancing Bounded Treewidth Circuits. In: Proeedings of CSR 2010 (to appear 2010)
Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. In: Proc. of STOC 1988, pp. 539–550 (1988)
Limaye, N., Mahajan, M., Sarma, M.N.J.: Upper bounds for monotone planar circuit value and variants. Computational Complexity 18(3), 377–412 (2009)
Markov, A.A.: On the inversion complexity of a system of functions. J. ACM 5(4), 331–334 (1958)
Markov, I.L., Shi, Y.: Simulating quantum computation by contracting tensor networks. SIAM J. Comput. 38(3), 963–981 (2008)
McColl, W.F.: On the planar monotone computation of threshold functions. In: Mehlhorn, K. (ed.) STACS 1985. LNCS, vol. 182, pp. 219–230. Springer, Heidelberg (1984)
Morizumi, H.: Limiting negations in formulas. In: Albers, S., et al. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 701–712. Springer, Heidelberg (2009)
Raz, R., Wigderson, A.: Monotone circuits for matching require linear depth. In: STOC 1990: Proceedings of the twenty-second annual ACM symposium on Theory of computing, pp. 287–292 (1990)
Razborov, A.A.: Lower bounds on the monotone complexity of some boolean functions. Soviet Math. Dokl. 281, 798–801 (1985)
Santha, M., Wilson, C.: Limiting negations in constant depth circuits. SIAM J. Comput. 22(2), 294–302 (1993)
Savage, J.E.: The performance of multilective vlsi algorithms. Journal of Computer and System Science 29(2), 243–273 (1984)
Sung, S.C., Tanaka, K.: Limiting negations in bounded-depth circuits: An extension of markovs theorem. In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol. 2906, pp. 108–116. Springer, Heidelberg (2003)
Tardos, E.: The Gap Between Monotone and Non-monotone Circuit Complexity is Exponential. Combinatorica 7, 393–394 (1987)
Valiant, L.G.: Short monotone formulae for the majority function. J. Algorithms 5(3), 363–366 (1984)
Vollmer, H.: Introduction to Circuit Complexity: A Uniform Approach. Springer, New York (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
He, J., Liang, H., Sarma, J.M.N. (2010). Limiting Negations in Bounded Treewidth and Upward Planar Circuits. In: Hliněný, P., Kučera, A. (eds) Mathematical Foundations of Computer Science 2010. MFCS 2010. Lecture Notes in Computer Science, vol 6281. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15155-2_37
Download citation
DOI: https://doi.org/10.1007/978-3-642-15155-2_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15154-5
Online ISBN: 978-3-642-15155-2
eBook Packages: Computer ScienceComputer Science (R0)