# Can reciprocal inputs speed up monotone computations?

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.