7
$\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$
4
$\begingroup$

I believe the answer to the Question 1 is negative.

We introduce an auxiliary circuit type: $P_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$. $P_1$-circuits are monotone circuits with all reciprocal inputs, and $P_{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.

$\endgroup$
  • $\begingroup$ Right, we can easily construct a circuit $C$ computing even the pair $(Q,M)$ such that $Q=F\cdot M$ (not just a circuit for the product polynomial $F\cdot M$). But how (even knowing $M$) to turn C into a circuit C' computing F? I mean: without cancellations at single gates, which is the essence of reciprocal inputs $1/x_i$? $\endgroup$ – Stasys Aug 15 at 12:23
  • 1
    $\begingroup$ In my old draft notices, I've now found how to get C' from C. If correct the resulting size is then $n\cdot s^2$, where $s$ is the size of C. I used the fact that no variable can appear in the monomial $M$ with degree larger than $2^s$. And yes, I also used gcd, albeit in terms of Minkowski $(\cup,+)$ circuits (producing the sets of exponent vectors of polynomials), not arithmetic $(+,\times)$ circuits, but this is only a notational issue. So, if you see some much simpler way to get C' from C, this would be interesting. $\endgroup$ – Stasys Aug 15 at 12:46
  • $\begingroup$ You are right, I did miss the fact that if we use an input in multiple gates, the monomials are different. We can multiply it by different monomials, increasing the size. $ns^2$ seems to be the right number of additional gates. My construction only works for formulas. $\endgroup$ – Vladimir Lysikov Aug 15 at 13:27
  • $\begingroup$ @Stasys Check out the edited answer, this is another way to present it. But it is likely the same construction you have. $\endgroup$ – Vladimir Lysikov Aug 15 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.