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?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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
-
-
2$\begingroup$ 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. $\endgroup$ – mikero Sep 15 '15 at 3:04
-
4
-
2$\begingroup$ 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. $\endgroup$ – Clement C. Sep 15 '15 at 13:27
-
2$\begingroup$ $2g+O(n\log n)$ is enough by dimacs.rutgers.edu/TechnicalReports/abstracts/1995/95-31.html . $\endgroup$ – Emil Jeřábek supports Monica Sep 16 '15 at 14:05
$\begingroup$
$\endgroup$
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.
