Can reciprocal inputs speed up monotone computations?

Question

A $(+,\times,1/x_i)$ circuit is a standard monotone arithmetic $(+,\times)$ circuit with the only difference that now besides the input variables $x_1,\ldots,x_n$, also their reciprocals $1/x_1,\ldots,1/x_n$ can be used as inputs.

That the gap (A) can be exponential was recently shown by Fomin, Grigoriev and Koshevoy: using ideas from electric network theory, they designed a $(+,\times,/)$ circuits of size $O(n^3)$ computing the generating polynomial of spanning trees of $n$-vertex graphs. This result is quite interesting: more than 35 years ago, Strassen has shown that division $(/)$ is useless, if we have subtraction $(-)$ in our disposal. So, an intact division taste on our calculator can still help, if the subtraction $(-)$ taste is long broken.

Thus, we now know that at least one of the gaps (B) and (C) must be exponential, but we do not know which.

Question 1: Can the gap (C) be exponential? That is, can the presence of reciprocal inputs $1/x_i$ substantially decrease the size of $(+,\times)$ circuits?

This question is related to the following question concerning the $(+,\times)$ complexity of polynomials and their "complements". Define the complement of a multilinear polynomial $f(x) = \sum_{S\in{\cal F}}\prod_{i\in S}x_i$ to be the multilinear polynomial co-$f = \sum_{S\in{\cal F}}\prod_{i\not\in S}x_i$. That is, monomials of co-$f$ are just complements of monomials of $f$.

Question 2: Can a polynomial $f$ require super-polynomially larger monotone arithmetic $(+,\times)$ circuits than its complement co-$f$?

An affirmative answer to Q2 would also answer Q1 in the affirmative: If the complement co-$f$ of an $n$-variate polynomial $f$ can be computed by a $(+,\times)$ circuit of size $s$, then $f$ can be computed by a $(+,\times,1/x_i)$ circuit of size $s+n$. To show this, suppose the complement co-$f(x) = \sum_{S\in{\cal F}}\prod_{i\not\in S}x_i$ has a $(+,\times)$ circuit $F(x)$ of size $s$. If we replace each input variable $x_i$ by its reciprocal $y_i=1/x_i$, then the obtained $(+,\times,1/x_i)$ circuit $F'$ computes a rational function of the form $f' =\sum_{S\in{\cal F}}\prod_{i\not\in S}y_i =\sum_{S\in{\cal F}}\prod_{i\not\in S}\frac{1}{x_i}$. If we take the monomial $M=x_1x_2\cdots x_n$, then the $(+,\times,1/x_i)$ circuit $M\cdot F'$ of size $s+n$ computes our original polynomial $M\cdot f'=f$.

Note 1: If instead of arithmetic $(+,\times)$ circuits we consider boolean $(\lor,\land)$ circuits, then the answer to Question 2 is YES: then the gap can be super-polynomial. Note that the complement co-$f$ of a monotone boolean function $f$ is neither its negation $\neg f$ nor its dual $\neg f(\neg x)$: minterms of co-$f$ are complements of the minterms of $f$.

To show the gap, consider the logical permanent function $\mathrm{Per}(x)$. This function has $n^2$ variables $x_e$, one for each edge of the complete bipartite $n\times n$ graph $K_{n,n}$. The function is an OR of $n!$ minterms, each corresponding to a perfect matching in $K_{n,n}$. Consider the boolean function $g$ on the same variables such that $g(x)=1$ iff the graph $G_x$ specified by $x$ is the complement of some (not necessarily perfect) matching. This happens iff every vertex of $K_{n,n}$ has degree $\geq n-1$ in $G_x$. This latter condition can be easily verified by a $(\lor,\land)$ circuit of size $O(n^4)$. Since the minterms of $g$ are complements of perfect matchings, $g$ is the complement co-$\mathrm{Per}$ of the permanent function. Thus, co-$\mathrm{Per}$ can be computed by a $(\lor,\land)$ circuit of size $O(n^4)$ but, as shown by Razborov, the function $\mathrm{Per}$ itself requires such circuits of size $n^{\Omega(\log n)}$. The reason why this argument does not answer Q2 in the arithmetic $(+,\times)$ case is that then all terms, not just shortest ones, do matter. So, then the polynomial $g$ does not compute the polynomial co-$\mathrm{Per}$.

Note 2: The weakness of arithmetic $(+,\times)$ circuits, in contrast to boolean $(\lor,\land)$ circuits, comes from them being unable to remove anything they produce under the way. Tropical $(\min,+)$ and $(\max,+)$ circuits (working over all nonnegative real numbers) constitute an intermediate model between boolean and arithmetic. They already can remove things via $\min(x,x+y)=x$ and $\max(x,x+y)=x+y$. So, perhaps Question 2 can be answered in the affirmative for tropical circuits? Note that over tropical $(\min,+)$ and $(\max,+)$ semirings, division $(/)$ corresponds to subtraction $(-)$. So, the corresponding chart (in the case of minimization) is:

That the gap (A) is exponential follows from the above mentioned upper bound $O(n^3)$ on the $(\min,+,-)$ circuit complexity of the MST problem (minimum weight spanning tree problem), and known exponential lower bounds on the $(\min,+)$ circuit complexity of MST, both for directed and undirected graphs.

Answer 1

I believe the answer to the Question 1 is negative.

We introduce an auxiliary circuit type: $X_k$-circuits have inputs $x_1, \dots, x_n$ and $1/x_k,\dots,1/x_n$ and have in addition to $+$ and $\times$ gates unary gates multiplying the input by $x_i^p$ for $i < k$, $p > 0$. $X_1$-circuits are monotone circuits with all reciprocal inputs, and $X_{n+1}$-circuits have no reciprocal inputs, but have multiplications by power of every monomial.

We transform an $X_k$-circuit computing a polynomial $F$ into an $X_{k + 1}$-circuit.

Each gate $g$ computes a Laurent polynomial $P_g$. Represent it as $P_g = x_k^{e_g} Q_g / M_g$ where $Q_g$ and $M_g$ are not divisible by $x_k$. We will transform the circuit in such a way that the corresponding gate in the transformed circuit computes $Q_g / M_g$.

Multiplication gates and multiplications by variable powers do not change. For addition $x_k^e Q / M = x_k^{e_1} Q_1 / M_1 + x_k^{e_2} Q_2 / M_2$ we will have $e = \min \{e_1, e_2\}$. W.l.o.g. $e_1 = e$, $e_2 = e + d$. Replace the addition gate by one addition and one power multiplication: $Q/M = Q_1 / M_1 + x_k^d Q_2 / M_2$.

In the end multiply the final result by appropriate power of $x_k$ if needed to get the required $F$.

In this way we transform an $X_k$-circuit with $a$ additions, $m$ multiplications and $p$ power-multiplications into an $X_{k + 1}$-circuit with $a$ additions, $m$ multiplications and at most $p + a + 1$ power-multiplications.

Doing this $n$ times to an $X_1$-ciruit with $a$ additions and $m$ multiplications we get a $X_{n + 1}$-circuit with $a$ additions, $m$ multiplications and at most $n(a + 1)$ power multiplications.

As Stasys notes in the comments, all powers involved are at most $2^m$, so we need at most $(a + 2)m$ multiplications to implement all $(a + 1)$ required powers of one variable. So we transformed a circuit with reciprocals with $a$ additions and $m$ multiplications into a circuit without reciprocals with $a$ additions and $m + n m (a + 2)$ multiplications.