1
$\begingroup$

This is a followup question to this other question, 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 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?

Improve this question
$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Or Meir
    Jan 3 at 9:11
  • $\begingroup$ 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. $\endgroup$
    – gigabytes
    Jan 3 at 9:38
  • $\begingroup$ Oh I see what you mean. I've clarified the question, if it helps. $\endgroup$
    – gigabytes
    Jan 3 at 10:04
  • 1
    $\begingroup$ 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 ... $\endgroup$
    – Emil Jeřábek
    Jan 3 at 12:00
  • 1
    $\begingroup$ ... 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. $\endgroup$
    – Emil Jeřábek
    Jan 3 at 12:04

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.