On the Mystery of Negations in Circuits: Structure vs Power

Exploring further the power of negations in Boolean circuits, in this paper we study the effect of interdependency of negation gates in circuits in terms of computational power. As a starting point, we study the power of independent negations (where no negation feeds into another, even via other gates) in circuits and show the following results.

• The minimum number of independent negations required to compute a Boolean function is exactly characterized by the decrease of the function. We also provide an additional characterization by a generalization of orientation [9], which we call the monotone orientation.

• We define a new measure called the thickness of a Boolean function, and show that if f has thickness at most t and has a circuit of depth d, then f can be computed using \(2^{\lceil \log (t+1)\rceil }\) (independent) negations in depth \(d+O(\log n)\). When the function is monotone, we also show a parameterized version of this result, where the depth is expressed in terms of thickness and d. Our techniques include a natural generalization of the Karchmer-Widgerson games to include a switch step.

• For functions with thickness t, we show that the monotone and non-monotone circuit depths are related by the factor of thickness and an extra \(O(\log n)\) additive factor. This generalizes the fact [16] that for slice functions, the monotone and non-monotone circuit depth complexities are related by an additive factor of \(O(\log n)\).

To go further, we study the dependency between negations in the circuit by modeling the same using a negation graph with negation gates (and root) as vertices and directed edges representing pair of negation gates which feed into each other through a path which does not have negations. We associate a measure of decrease capacity with the negation graph, denoted \(\mathsf{d_{\max }}\). We show the following results:

• For a negation graph N, \(\mathsf{d_{\max }}(N)\) is the maximum decrease of any circuit which has this negation graph. Using this as a tool, we derive necessary conditions on the structure of negation graphs when the circuit is negation optimal.

• We show how to construct circuits for a function f, given a negation tree with decrease capacity at least \(\frac{\mathsf {alt}(f)}{2}\). En route this result, we show that if f and g are two Boolean functions on n variables with \(\mathsf {alt}(f) \le \mathsf {alt}(g)\) and \(f(0^n)=g(0^n)\), then any circuit for g can be used (with substitution of variables with monotone functions) to compute f without using any extra negation. This may be of independent interest.

1. 1.

   The actual bound in [10] is stated in terms of the measure of non-monotonicity of a function called decrease (which we denote by \(\mathsf{dec}(f)\)) - see Sect. 2 for definition).

2. 2.

   Informally, this is the number of negations that any De-Morgan circuits requires, to compute the function.

3. 3.

   When the circuit is viewed as a graph, the negation gates represent an independent set.

4. 4.

   Not even through a series of gates.

5. 5.

   Alice and Bob must both know that they are performing the operation. This can be inferred from the communication or can be indicated by one player by communicating with the other.

6. 6.

   If the root gate is a negation gate, add a dummy gate as a root gate.

Authors and Affiliations

1. Indian Institute of Technology Madras, Chennai, India

   Prashanth Amireddy, Sai Jayasurya & Jayalal Sarma

Corresponding author

Correspondence to Jayalal Sarma .

Editors and Affiliations

1. Georgia State University, Atlanta, USA

   Donghyun Kim

2. Department of Mathematics and Physics, North Carolina Central University, Durham, NC, USA

   R. N. Uma

3. Computer Science, Georgia State University, Atlanta, GA, USA

   Zhipeng Cai

4. Korea University, Seoul, Korea (Republic of)

   Dong Hoon Lee

Reprints and permissions

© 2020 Springer Nature Switzerland AG

Policies and ethics