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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.