How many negations do we need to compute monotone functions?

Question

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?

Answer 1

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

Answer 2

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.