<h1>How to compute the inversion of $2^n-1$ bits using $n$ negations</h1>

<p>Let the bits $x_0, \ldots, x_{2^n-1}$ be sorted in the decreasing order, i.e.
$i&lt;j$ implies $x_i \ge x_j$. This can be achieved by a monotone sorting network like the Ajtai–Komlós–Szemerédi sorting network. </p>

<p>We define the inversion circuit for $2^n-1$ bits $I^n(\vec{x})$ inductively:
For the base case we have $n=1$ and $I^1_0(\vec{x}) := \lnot x_0$.
 Let $m=2^{n-1}$. We reduce $I^n$ (for $2m+1$) bits to one $I^{n-1}$ gate (for $m$ bits) and one negation gate using $\land$ and $\lor$ gates. We use negation to compute $\lnot x_m$. For $i&lt;m$ let $y_i := (x_i \land \lnot x_m) \lor x_{m+i}$. We use $I^{n-1}$ to invert $\vec{y}$. Now we can define $I^n$ as follows:</p>

<p>$$I^n_i := \begin{cases}
I^{n-1}_i(\vec{y}) \land \lnot x_m &amp; i&lt;m \\
\lnot x_m &amp; i=m \\
I^{n-1}_i(\vec{y}) \lor \lnot x_m &amp; i&lt;m \\
\end{cases}$$</p>

<p>It is easy to verify this inverts $\vec{x}$ by considering the possible values of $x_n$ and using the fact that $\vec{x}$ is decreasing.</p>

<p>From Michael J. Fischer, The complexity of negation-limited networks - a brief survey, 1975.</p>

CC BY-SA 3.0
2016-04-17T19:51:47.370Z
2016-04-17T19:59:06.020Z
2016-04-17T19:59:06.020Z
Anonymous
<p>Markov proved that <em>any</em> function of <span class="math-container">$n$</span> inputs can be computed with only <span class="math-container">$\lceil \log (n+1)\rceil$</span> negations. An efficient constructive version was described by Fisher. See also an exposition of the result from the <a href="https://rjlipton.wordpress.com/2013/12/26/re-gifting-an-old-theorem/" rel="noreferrer">GLL blog</a>.</p>
<p>More precisely:</p>
<blockquote>
<p><strong>Theorem:</strong> Suppose <span class="math-container">$f : \{0,1\}^n \to \{0,1\}^m$</span> is computed by a circuit <span class="math-container">$C$</span> with <span class="math-container">$g$</span> gates, then it is also computed by a circuit <span class="math-container">$C^*$</span> with <span class="math-container">$2g + O(n^2 \log^2 n)$</span> gates and <span class="math-container">$\lceil \log (n+1) \rceil$</span> negations.</p>
</blockquote>
<p>The main idea is to add for each wire <span class="math-container">$w$</span> in <span class="math-container">$C$</span> a parellel wire <span class="math-container">$w'$</span> in <span class="math-container">$C^*$</span> that always carries the complement of <span class="math-container">$w$</span>. The base case is for the input wires: Fisher describes how to construct an inversion circuit <span class="math-container">$I(x) = \overline x$</span> with <span class="math-container">$O(n^2 \log^2 n)$</span> gates and only  <span class="math-container">$\lceil \log (n+1) \rceil$</span> negations. For the AND gates of circuit <span class="math-container">$C$</span>, we can augment <span class="math-container">$a = b \land c$</span> with <span class="math-container">$a' = b' \lor c'$</span>, and likewise for OR gates. NOT gates in <span class="math-container">$C$</span> cost nothing, we just swap the roles of <span class="math-container">$w$</span> and <span class="math-container">$w'$</span> downstream of the NOT gate. In this way, the entire circuit besides the inverter subcircuit is monotone.</p>
<blockquote>
<p>A. A. Markov. On the inversion complexity of a system of functions. <em>J. ACM</em>, 5(4):331–334, 1958.</p>
<p>M. J. Fischer. The complexity of negation-limited networks - A brief survey. In
<em>Automata Theory and Formal Languages</em>, 71–82, 1975</p>
</blockquote>

CC BY-SA 3.0
2015-09-15T02:16:19.437Z
Is it a P/poly circuit?
Anonymous
CC BY-SA 3.0
2015-09-15T03:04:48.633Z
Yes, the size of the circuit goes from $g$ to $2g + O(n^2 \log^2 n)$ where $n$ is the number of inputs. I have expanded the response to include a more precise statement of the result, and make it more self-contained.
mikero
CC BY-SA 3.0
2015-09-15T08:22:10.863Z
And some explicit (multi-output) monotone functions in P/poly [require](http://www.sciencedirect.com/science/article/pii/S0020019003004770) at least $\log n-O(\log\log n)$ negations to remain in P/poly.
Stasys
CC BY-SA 3.0
2015-09-15T13:12:30.930Z
It is surprising $\log n$ negations suffice. Thank you.
Anonymous
CC BY-SA 3.0
2015-09-15T13:27:06.890Z
For this line of questions (power of negations in circuits/formulae/etc), the following may be relevant: http://eccc.hpi-web.de/report/2014/144/, https://eprint.iacr.org/2014/902, and  http://eccc.hpi-web.de/report/2015/026/.
Clement C.
CC BY-SA 3.0
2015-09-16T14:05:51.187Z
$2g+O(n\log n)$ is enough by http://dimacs.rutgers.edu/TechnicalReports/abstracts/1995/95-31.html .
Emil Jeřábek
CC BY-SA 3.0
2016-04-17T23:52:17.937Z
For a minute I thought this was *the* A. A. Markov, but it seems to be published too late.
Sasho Nikolov
CC BY-SA 3.0
2015-09-14T21:48:33.023Z
2015-09-15T03:04:07.317Z
2020-06-17T09:38:08.363Z
mikero
<p>Razborov proved that the monotone function matching is not in <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:M#mp">mP</a>. But can we compute matching using a polynomial size circuit with a few negations? Is there a P/poly circuit with $O(n^\epsilon)$ negations that computes matching? What is the trade-off between the number of negations and the size for matching?</p>

<cc.complexity-theory><circuit-complexity><lower-bounds><matching><monotone>
How many negations do we need to compute monotone functions?
Anonymous
# How many negations do we need to compute monotone functions?

(Asked by: username_0 on 2015-09-14)

Razborov proved that the monotone function matching is not in [mP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:M#mp). But can we compute matching using a polynomial size circuit with a few negations? Is there a P/poly circuit with $O(n^\epsilon)$ negations that computes matching? What is the trade-off between the number of negations and the size for matching?

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, matching, monotone


---

## 2 answers

### Answer by username_1 on 2015-09-14. Score: 21 | Accepted answer

Markov proved that *any* function of $n$ inputs can be computed with only $\lceil \log (n+1)\rceil$ negations. An efficient constructive version was described by Fisher. See also an exposition of the result from the [GLL blog](https://rjlipton.wordpress.com/2013/12/26/re-gifting-an-old-theorem/).

More precisely:

> **Theorem:** Suppose $f : \{0,1\}^n \to \{0,1\}^m$ is computed by a circuit $C$ with $g$ gates, then it is also computed by a circuit $C^\*$ with $2g + O(n^2 \log^2 n)$ gates and $\lceil \log (n+1) \rceil$ negations.

The main idea is to add for each wire $w$ in $C$ a parellel wire $w'$ in $C^\*$ that always carries the complement of $w$. The base case is for the input wires: Fisher describes how to construct an inversion circuit $I(x) = \overline x$ with $O(n^2 \log^2 n)$ gates and only $\lceil \log (n+1) \rceil$ negations. For the AND gates of circuit $C$, we can augment $a = b \land c$ with $a' = b' \lor c'$, and likewise for OR gates. NOT gates in $C$ cost nothing, we just swap the roles of $w$ and $w'$ downstream of the NOT gate. In this way, the entire circuit besides the inverter subcircuit is monotone.

> A. A. Markov. On the inversion complexity of a system of functions. *J. ACM*, 5(4):331–334, 1958.
>
> M. J. Fischer. The complexity of negation-limited networks - A brief survey. In
> *Automata Theory and Formal Languages*, 71–82, 1975

> **Comments:**
> **username_0**: Is it a P/poly circuit?  
> **username_1**: Yes, the size of the circuit goes from $g$ to $2g + O(n^2 \log^2 n)$ where $n$ is the number of inputs. I have expanded the response to include a more precise statement of the result, and make it more self-contained.  
> **username_2**: And some explicit (multi-output) monotone functions in P/poly [require](http://www.sciencedirect.com/science/article/pii/S0020019003004770) at least $\log n-O(\log\log n)$ negations to remain in P/poly.  
> **username_0**: It is surprising $\log n$ negations suffice. Thank you.  
> **username_3**: For this line of questions (power of negations in circuits/formulae/etc), the following may be relevant: http://eccc.hpi-web.de/report/2014/144/, https://eprint.iacr.org/2014/902, and  http://eccc.hpi-web.de/report/2015/026/.  
> **username_4**: $2g+O(n\log n)$ is enough by http://dimacs.rutgers.edu/TechnicalReports/abstracts/1995/95-31.html .  
> **username_5**: For a minute I thought this was *the* A. A. Markov, but it seems to be published too late.  

---

### Answer by username_0 on 2016-04-17. Score: 1

# How to compute the inversion of $2^n-1$ bits using $n$ negations

Let the bits $x\_0, \ldots, x\_{2^n-1}$ be sorted in the decreasing order, i.e.
$i

We define the inversion circuit for $2^n-1$ bits $I^n(\vec{x})$ inductively:
For the base case we have $n=1$ and $I^1\_0(\vec{x}) := \lnot x\_0$.
Let $m=2^{n-1}$. We reduce $I^n$ (for $2m+1$) bits to one $I^{n-1}$ gate (for $m$ bits) and one negation gate using $\land$ and $\lor$ gates. We use negation to compute $\lnot x\_m$. For $i

$$I^n\_i := \begin{cases}
I^{n-1}\_i(\vec{y}) \land \lnot x\_m & i

It is easy to verify this inverts $\vec{x}$ by considering the possible values of $x\_n$ and using the fact that $\vec{x}$ is decreasing.

From Michael J. Fischer, The complexity of negation-limited networks - a brief survey, 1975.


---

