# How many negations do we need to compute monotone functions?

Razborov proved that the monotone function matching is not in 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?

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.

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

• Is it a P/poly circuit? Sep 15 '15 at 2:16
• 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. Sep 15 '15 at 3:04
• And some explicit (multi-output) monotone functions in P/poly require at least $\log n-O(\log\log n)$ negations to remain in P/poly. Sep 15 '15 at 8:22
• For this line of questions (power of negations in circuits/formulae/etc), the following may be relevant: eccc.hpi-web.de/report/2014/144, eprint.iacr.org/2014/902, and eccc.hpi-web.de/report/2015/026. Sep 15 '15 at 13:27
• $2g+O(n\log n)$ is enough by dimacs.rutgers.edu/TechnicalReports/abstracts/1995/95-31.html . Sep 16 '15 at 14:05

# 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<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.

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<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:

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

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.