6
$\begingroup$

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.

a chart for arithmetic circuits

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:

a chart for tropical circuits

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.