<p>This is a followup question to <a href="https://cstheory.stackexchange.com/q/52335/18101">this other question</a>, where I was told that <em>multiplication</em> is in <span class="math-container">$NC^1$</span> so can be computed with a circuit of polynomial size and logarithmic depth, hence also with a Boolean <strong>formula</strong> of polynomial size. This in particular also work for <em>addition</em> which is even in <span class="math-container">$AC^0$</span> as far as I know.</p>
<p>But then, still because I'm not at all familiar with circuit complexity issues, it is not clear to me if these results can be composed to compute arbitrary arithmetic expressions. The syntax of such expressions is something like:</p>
<p><span class="math-container">\begin{equation*}
  e \equiv k \mid x \mid e + e \mid e\cdot e
\end{equation*}</span>
where <span class="math-container">$k\in\mathbb{Z}$</span> and <span class="math-container">$x$</span> is an input variable.</p>
<p>For example something like <span class="math-container">$(2xy+5)(3x-3)$</span>, <em>i.e.</em> polynomials, but not necessarily in standard form. It seems to me that composing naively the circuits leads to something of polynomial depth, so the formulas would become potentially exponential. Am I missing something?</p>
<p>Which is the <strong>formula</strong> complexity of computing arithmetic expressions like the above?</p>
<p><strong>Clarification</strong>: thanks to the comments I realized the question is bit vague. The circuit complexity is usually measured in terms of the size of the inputs (<span class="math-container">$x$</span>, <span class="math-container">$y$</span>, <span class="math-container">$\ldots$</span>), but here we have another parameter which is the size of the expression. So what I would need is the circuit complexity of the whole class of these arithmetic expressions in terms of the size of the input variables and the size of the expression itself.</p>
<p><strong>Edit</strong>: looking around made me realize that my problem is in fact a very basic question about <strong>arithmetic circuits</strong>. So I found <a href="https://www.sciencedirect.com/science/article/pii/089054019190078G" rel="nofollow noreferrer">this reference</a> which seems exactly what I need. <em>Proposition 3.1</em> there says that over a finite field <span class="math-container">$\mathbb{F}_p$</span>, an arithmetic circuit without division of depth <span class="math-container">$d$</span> can be simulated by a Boolean circuit of depth <span class="math-container">$\mathcal{O}(d\log\log p)$</span>.</p>
<p>This <strong>almost</strong> fits my case because I'm working on <span class="math-container">$m$</span>-bits integers so it's not a finite field <span class="math-container">$\mathbb{F}_p$</span> with <span class="math-container">$p$</span> prime, but can the result be adapted in some way?</p>

CC BY-SA 4.0
2023-01-03T09:11:08.027Z
This question is too vague. There are many different arithmetic expressions, and each of them may have different formula complexity.
Expressions that use a constant number of arithmetic operations, such as the one in your question, can be computed by polynomial size formula by composing the formulas for each of the operations in the naive way.
Or Meir
CC BY-SA 4.0
2023-01-03T09:38:11.383Z
Hi, thanks for the feedback. The question includes the grammar of the expressions I'm interested in. I'm interested in the formula complexity of the class of expressions made of that syntax, in terms of the size of the expression.
Nicola Gigante
CC BY-SA 4.0
2023-01-03T10:04:37.530Z
Oh I see what you mean. I've clarified the question, if it helps.
Nicola Gigante
CC BY-SA 4.0
2023-01-03T12:00:26.603Z
Since you talk about *expressions*, I assume you mean arithmetic formulas rather than arithmetic circuits. Evaluation of arithmetic formulas (over $\mathbb Z$) can be done in the class $\mathrm{GapNC^1}$ defined in Caussinus, McKenzie, Thérien & Vollmer, *Nondeterministic $\mathit{NC}^1$ computation*; this amounts to the fact that any such arithmetic formula can be balanced in $\mathrm{TC}^0$ to logarithmic depth, which goes back to Buss, Cook, Gupta & Ramachandran, *An optimal parallel algorithm for formula evaluation*, and is proved as a consequence of more general results in ...
Emil Jeřábek
CC BY-SA 4.0
2023-01-03T12:04:27.663Z
... Ganardi & Lohrey, *A universal tree balancing theorem*, and earlier in Krebs, Limaye & Ludwig, *A unified method for placing problems in polylogarithmic depth*. In turn, $\mathrm{GapNC^1}$ is included in FL, and as mentioned in the Caussinus et al. paper, can be simulated by Boolean circuits of depth $O(\log n\,\log^*n)$, with a reference to a paper by Jung.
Emil Jeřábek
CC BY-SA 4.0
2023-01-03T12:26:14.593Z
Thanks, very precise as always! I'll parse all the references and get back if needed.
Nicola Gigante
CC BY-SA 4.0
2023-01-03T12:34:28.827Z
Here I am already. The fact that arithmetic formulas over $\mathbb{Z}$ can be evaluated in $\mathrm{GapNC}^1$ is proved in Caussinus *et al.* or is there another reference  for that?
Nicola Gigante
CC BY-SA 4.0
2023-01-03T13:06:03.453Z
All the *other* references I gave.
Emil Jeřábek
CC BY-SA 4.0
2023-01-03T13:48:33.797Z
LoL, ok, I parsed your comment again and it all makes sense now, thanks again!
Nicola Gigante
<circuit-complexity><arithmetic-circuits>
Boolean formula complexity of arithmetic expressions
Nicola Gigante
# Boolean formula complexity of arithmetic expressions

(Asked by: username_0 on 2023-01-03)

This is a followup question to [this other question](https://cstheory.stackexchange.com/q/52335/18101), where I was told that *multiplication* is in $NC^1$ so can be computed with a circuit of polynomial size and logarithmic depth, hence also with a Boolean **formula** of polynomial size. This in particular also work for *addition* which is even in $AC^0$ as far as I know.

But then, still because I'm not at all familiar with circuit complexity issues, it is not clear to me if these results can be composed to compute arbitrary arithmetic expressions. The syntax of such expressions is something like:

\begin{equation\*}
e \equiv k \mid x \mid e + e \mid e\cdot e
\end{equation\*}
where $k\in\mathbb{Z}$ and $x$ is an input variable.

For example something like $(2xy+5)(3x-3)$, *i.e.* polynomials, but not necessarily in standard form. It seems to me that composing naively the circuits leads to something of polynomial depth, so the formulas would become potentially exponential. Am I missing something?

Which is the **formula** complexity of computing arithmetic expressions like the above?

**Clarification**: thanks to the comments I realized the question is bit vague. The circuit complexity is usually measured in terms of the size of the inputs ($x$, $y$, $\ldots$), but here we have another parameter which is the size of the expression. So what I would need is the circuit complexity of the whole class of these arithmetic expressions in terms of the size of the input variables and the size of the expression itself.

**Edit**: looking around made me realize that my problem is in fact a very basic question about **arithmetic circuits**. So I found [this reference](https://www.sciencedirect.com/science/article/pii/089054019190078G) which seems exactly what I need. *Proposition 3.1* there says that over a finite field $\mathbb{F}\_p$, an arithmetic circuit without division of depth $d$ can be simulated by a Boolean circuit of depth $\mathcal{O}(d\log\log p)$.

This **almost** fits my case because I'm working on $m$-bits integers so it's not a finite field $\mathbb{F}\_p$ with $p$ prime, but can the result be adapted in some way?

**Tags:** circuit-complexity, arithmetic-circuits

> **Comments:**
> **username_1**: This question is too vague. There are many different arithmetic expressions, and each of them may have different formula complexity. Expressions that use a constant number of arithmetic operations, such as the one in your question, can be computed by polynomial size formula by composing the formulas for each of the operations in the naive way.  
> **username_0**: Hi, thanks for the feedback. The question includes the grammar of the expressions I'm interested in. I'm interested in the formula complexity of the class of expressions made of that syntax, in terms of the size of the expression.  
> **username_0**: Oh I see what you mean. I've clarified the question, if it helps.  
> **username_2**: Since you talk about *expressions*, I assume you mean arithmetic formulas rather than arithmetic circuits. Evaluation of arithmetic formulas (over $\mathbb Z$) can be done in the class $\mathrm{GapNC^1}$ defined in Caussinus, McKenzie, Thérien & Vollmer, *Nondeterministic $\mathit{NC}^1$ computation*; this amounts to the fact that any such arithmetic formula can be balanced in $\mathrm{TC}^0$ to logarithmic depth, which goes back to Buss, Cook, Gupta & Ramachandran, *An optimal parallel algorithm for formula evaluation*, and is proved as a consequence of more general results in ...  
> **username_2**: ... Ganardi & Lohrey, *A universal tree balancing theorem*, and earlier in Krebs, Limaye & Ludwig, *A unified method for placing problems in polylogarithmic depth*. In turn, $\mathrm{GapNC^1}$ is included in FL, and as mentioned in the Caussinus et al. paper, can be simulated by Boolean circuits of depth $O(\log n\,\log^*n)$, with a reference to a paper by Jung.  
> **username_0**: Thanks, very precise as always! I'll parse all the references and get back if needed.  
> **username_0**: Here I am already. The fact that arithmetic formulas over $\mathbb{Z}$ can be evaluated in $\mathrm{GapNC}^1$ is proved in Caussinus *et al.* or is there another reference  for that?  
> **username_2**: All the *other* references I gave.  
> **username_0**: LoL, ok, I parsed your comment again and it all makes sense now, thanks again!  

---

## 0 answers

