<p>I believe the answer to the Question 1 is negative.</p>

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

<p>We transform an <span class="math-container">$X_k$</span>-circuit computing a polynomial <span class="math-container">$F$</span> into an <span class="math-container">$X_{k + 1}$</span>-circuit.</p>

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

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

<p>In the end multiply the final result by appropriate power of <span class="math-container">$x_k$</span> if needed to get the required <span class="math-container">$F$</span>.</p>

<p>In this way we transform an <span class="math-container">$X_k$</span>-circuit with <span class="math-container">$a$</span> additions, <span class="math-container">$m$</span> multiplications and <span class="math-container">$p$</span> power-multiplications into an <span class="math-container">$X_{k + 1}$</span>-circuit with <span class="math-container">$a$</span> additions, <span class="math-container">$m$</span> multiplications and at most <span class="math-container">$p + a + 1$</span> power-multiplications.</p>

<p>Doing this <span class="math-container">$n$</span> times to an <span class="math-container">$X_1$</span>-ciruit with <span class="math-container">$a$</span> additions and <span class="math-container">$m$</span> multiplications we get a <span class="math-container">$X_{n + 1}$</span>-circuit with <span class="math-container">$a$</span> additions, <span class="math-container">$m$</span> multiplications and at most <span class="math-container">$n(a + 1)$</span> power multiplications.</p>

<p>As Stasys notes in the comments, all powers involved are at most <span class="math-container">$2^m$</span>, so we need at most <span class="math-container">$(a + 2)m$</span> multiplications to implement all <span class="math-container">$(a + 1)$</span> required powers of one variable. So we transformed a circuit with reciprocals with <span class="math-container">$a$</span> additions and <span class="math-container">$m$</span> multiplications into a circuit without reciprocals with <span class="math-container">$a$</span> additions and <span class="math-container">$m + n m (a + 2)$</span> multiplications.</p>

CC BY-SA 4.0
2019-08-15T12:23:55.520Z
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$?
Stasys
CC BY-SA 4.0
2019-08-15T12:46:28.300Z
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.
Stasys
CC BY-SA 4.0
2019-08-15T13:27:36.940Z
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.
Vladimir Lysikov
CC BY-SA 4.0
2019-08-15T14:37:05.830Z
@Stasys Check out the edited answer, this is another way to present it. But it is likely the same construction you have.
Vladimir Lysikov
CC BY-SA 4.0
2019-08-27T06:33:01.120Z
Yes, my proof in old notes was similar, but more "global" (with a goal to show the same also for topical circuits). But your idea to eliminate reciprocal inputs one-by-one is just nice! So, under proviso that "substantially" means "more than quadraticaly", both my questions are answered.
Stasys
CC BY-SA 4.0
2019-08-14T18:35:48.357Z
2019-08-27T11:20:51.367Z
2019-08-27T11:20:51.367Z
Vladimir Lysikov
<p>A <span class="math-container">$(+,\times,1/x_i)$</span> circuit is a standard monotone arithmetic <span class="math-container">$(+,\times)$</span> circuit with the only difference that now  besides the input variables <span class="math-container">$x_1,\ldots,x_n$</span>, also their reciprocals  <span class="math-container">$1/x_1,\ldots,1/x_n$</span> can be used as inputs.</p>
<p>
<p><a href="https://i.sstatic.net/ezHXO.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ezHXO.png" alt="a chart for arithmetic circuits" /></a></p>
<p>That the gap (A) can be exponential was recently shown by <a href="https://arxiv.org/abs/1307.8425" rel="nofollow noreferrer">Fomin, Grigoriev and Koshevoy</a>: using ideas from electric network theory, they designed a <span class="math-container">$(+,\times,/)$</span> circuits of size <span class="math-container">$O(n^3)$</span> computing the generating polynomial of spanning trees of <span class="math-container">$n$</span>-vertex graphs. This result is quite interesting: more than 35 years ago,  <a href="http://www.thi.informatik.uni-frankfurt.de/%7Ejukna/Strassen-Vermeidung-von-Divisionen.pdf" rel="nofollow noreferrer">Strassen</a> has shown that division <span class="math-container">$(/)$</span> is <i>useless</i>, if we have subtraction <span class="math-container">$(-)$</span> in our disposal. So, an intact division taste on our calculator <i>can</i> still help, if the subtraction <span class="math-container">$(-)$</span> taste is long broken.</p>
<p>Thus, we now know that at least one of the gaps (B) and (C) must be exponential, but we do not know which.</p>
 <blockquote>
<b>Question 1:</b>
Can the gap (C) be exponential? That is, can the presence of reciprocal inputs <span class="math-container">$1/x_i$</span>
 substantially decrease the size of <span class="math-container">$(+,\times)$</span> circuits?
</blockquote>
<p>This question is related to the following question concerning the <span class="math-container">$(+,\times)$</span> complexity of polynomials and their &quot;complements&quot;.
Define the <i>complement</i> of a
multilinear polynomial <span class="math-container">$f(x) = \sum_{S\in{\cal F}}\prod_{i\in S}x_i$</span> to be the
multilinear polynomial co-<span class="math-container">$f = \sum_{S\in{\cal F}}\prod_{i\not\in S}x_i$</span>. That is, monomials of co-<span class="math-container">$f$</span> are just complements of monomials of <span class="math-container">$f$</span>.</p>
<blockquote>
<b>Question 2:</b> Can a polynomial <span class="math-container">$f$</span> require super-polynomially larger monotone arithmetic <span class="math-container">$(+,\times)$</span> circuits than its complement co-<span class="math-container">$f$</span>?
</blockquote>
An affirmative answer to Q2 would also answer Q1 in the affirmative:
If the complement co-<span class="math-container">$f$</span> of an <span class="math-container">$n$</span>-variate polynomial <span class="math-container">$f$</span> can be computed by a <span class="math-container">$(+,\times)$</span> circuit of size <span class="math-container">$s$</span>, then <span class="math-container">$f$</span> can be computed by a <span class="math-container">$(+,\times,1/x_i)$</span> circuit of size <span class="math-container">$s+n$</span>.
To show this, suppose the complement co-<span class="math-container">$f(x) = \sum_{S\in{\cal F}}\prod_{i\not\in S}x_i$</span> has a <span class="math-container">$(+,\times)$</span> circuit <span class="math-container">$F(x)$</span> of size <span class="math-container">$s$</span>. If we replace each input variable <span class="math-container">$x_i$</span> by its reciprocal <span class="math-container">$y_i=1/x_i$</span>, then the obtained <span class="math-container">$(+,\times,1/x_i)$</span> circuit <span class="math-container">$F'$</span> computes a rational function of the form <span class="math-container">$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}$</span>. If we take the monomial <span class="math-container">$M=x_1x_2\cdots x_n$</span>, then the <span class="math-container">$(+,\times,1/x_i)$</span> circuit <span class="math-container">$M\cdot F'$</span> of size <span class="math-container">$s+n$</span> computes our original polynomial <span class="math-container">$M\cdot f'=f$</span>.
<p>
<b>Note 1:</b> If instead of arithmetic  <span class="math-container">$(+,\times)$</span> circuits we  consider <i>boolean</i>  <span class="math-container">$(\lor,\land)$</span> circuits, then the  answer to Question 2 is YES: then the gap <i>can</i> be super-polynomial. Note that the complement co-<span class="math-container">$f$</span> of a monotone boolean function <span class="math-container">$f$</span> is neither its negation <span class="math-container">$\neg f$</span> nor its dual <span class="math-container">$\neg f(\neg x)$</span>: minterms of co-<span class="math-container">$f$</span> are complements of the minterms of <span class="math-container">$f$</span>.
<p>
To show the gap, consider the logical permanent function <span class="math-container">$\mathrm{Per}(x)$</span>. This function has <span class="math-container">$n^2$</span> variables <span class="math-container">$x_e$</span>, one for each edge of the complete bipartite <span class="math-container">$n\times n$</span> graph <span class="math-container">$K_{n,n}$</span>. The function is an OR of <span class="math-container">$n!$</span> minterms, each corresponding to a perfect matching in <span class="math-container">$K_{n,n}$</span>.
Consider the boolean function <span class="math-container">$g$</span> on the same variables such that <span class="math-container">$g(x)=1$</span> iff the graph <span class="math-container">$G_x$</span> specified by <span class="math-container">$x$</span> is the complement of some (not necessarily perfect) matching. This happens iff every vertex of <span class="math-container">$K_{n,n}$</span> has degree <span class="math-container">$\geq n-1$</span> in <span class="math-container">$G_x$</span>. This latter condition can be easily verified by a <span class="math-container">$(\lor,\land)$</span> circuit of size <span class="math-container">$O(n^4)$</span>. Since the <i>minterms</i>  of <span class="math-container">$g$</span>  are complements of perfect matchings, <span class="math-container">$g$</span> is the complement co-<span class="math-container">$\mathrm{Per}$</span> of the permanent function. Thus, co-<span class="math-container">$\mathrm{Per}$</span> <i>can</i> be computed by a <span class="math-container">$(\lor,\land)$</span> circuit of size <span class="math-container">$O(n^4)$</span> but, as shown by Razborov, the function <span class="math-container">$\mathrm{Per}$</span> itself requires such circuits of size <span class="math-container">$n^{\Omega(\log n)}$</span>.
The reason why this argument does not answer Q2 in the arithmetic <span class="math-container">$(+,\times)$</span> case is that then <i>all</i> terms, not just shortest ones, do matter. So, then the polynomial <span class="math-container">$g$</span> does <i>not</i> compute the polynomial  co-<span class="math-container">$\mathrm{Per}$</span>.
<p><b>Note 2:</b>  The weakness of arithmetic <span class="math-container">$(+,\times)$</span> circuits, in contrast to boolean <span class="math-container">$(\lor,\land)$</span> circuits, comes from them being unable to remove anything they produce under the way. <a href="https://en.wikipedia.org/wiki/Tropical_semiring" rel="nofollow noreferrer">Tropical</a> <span class="math-container">$(\min,+)$</span> and <span class="math-container">$(\max,+)$</span> circuits (working over all nonnegative real numbers) constitute an intermediate model between boolean and arithmetic. They already <i>can</i> remove things via <span class="math-container">$\min(x,x+y)=x$</span> and <span class="math-container">$\max(x,x+y)=x+y$</span>. So, perhaps Question 2 can be answered in the affirmative for tropical circuits? Note that over tropical <span class="math-container">$(\min,+)$</span> and <span class="math-container">$(\max,+)$</span> semirings, division <span class="math-container">$(/)$</span> corresponds to subtraction <span class="math-container">$(-)$</span>. So, the corresponding chart (in the case of minimization) is:</p>
<p><a href="https://i.sstatic.net/mxcfJ.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/mxcfJ.png" alt="a chart for tropical circuits" /></a></p>
<p>That the gap (A) is exponential follows from the above mentioned upper bound <span class="math-container">$O(n^3)$</span> on the <span class="math-container">$(\min,+,-)$</span> circuit complexity of the MST problem (minimum weight spanning tree problem), and known exponential lower bounds on the <span class="math-container">$(\min,+)$</span> circuit complexity of MST, both for <a href="https://web.vu.lt/mif/s.jukna/ftp/Jerrum-Snir.pdf" rel="nofollow noreferrer">directed</a> and <a href="https://web.vu.lt/mif/s.jukna/ftp/spanntree-rev.pdf" rel="nofollow noreferrer">undirected</a> graphs.</p>

<cc.complexity-theory><circuit-complexity><algebraic-complexity><arithmetic-circuits>
Can reciprocal inputs speed up monotone computations?
Stasys
# Can reciprocal inputs speed up monotone computations?

(Asked by: username_0 on 2019-02-09)

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](https://i.sstatic.net/ezHXO.png)](https://i.sstatic.net/ezHXO.png)

That the gap (A) can be exponential was recently shown by [Fomin, Grigoriev and Koshevoy](https://arxiv.org/abs/1307.8425): 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](http://www.thi.informatik.uni-frankfurt.de/%7Ejukna/Strassen-Vermeidung-von-Divisionen.pdf) 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](https://en.wikipedia.org/wiki/Tropical_semiring) $(\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](https://i.sstatic.net/mxcfJ.png)](https://i.sstatic.net/mxcfJ.png)

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](https://web.vu.lt/mif/s.jukna/ftp/Jerrum-Snir.pdf) and [undirected](https://web.vu.lt/mif/s.jukna/ftp/spanntree-rev.pdf) graphs.

**Tags:** cc.complexity-theory, circuit-complexity, algebraic-complexity, arithmetic-circuits


---

## 1 answers

### Answer by username_1 on 2019-08-14. Score: 4 | Accepted answer

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 username_0 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.

> **Comments:**
> **username_0**: 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$?  
> **username_0**: 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.  
> **username_1**: 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.  
> **username_1**: @username_0 Check out the edited answer, this is another way to present it. But it is likely the same construction you have.  
> **username_0**: Yes, my proof in old notes was similar, but more "global" (with a goal to show the same also for topical circuits). But your idea to eliminate reciprocal inputs one-by-one is just nice! So, under proviso that "substantially" means "more than quadraticaly", both my questions are answered.  

---

