<p>Multiplication is well known to be computable in uniform <span class="math-container">$\mathrm{TC}^0$</span>, i.e., by a DLOGTIME-uniform family of constant-depth polynomial-size circuits using (unbounded fan-in) <span class="math-container">$\land$</span>, <span class="math-container">$\lor$</span>, <span class="math-container">$\neg$</span>, and Majority gates. In fact, multiplication is <span class="math-container">$\mathrm{TC}^0$</span>-complete under <span class="math-container">$\mathrm{AC}^0$</span> Turing reductions.</p>
<p>Consequently, it is also computable in uniform <span class="math-container">$\mathrm{NC}^1$</span>, i.e., by a DLOGTIME-uniform family of bounded fan-in Boolean formulas or circuits of depth <span class="math-container">$O(\log n)$</span> (thus of polynomial size). Here, uniformity is with respect to the usual infix or prefix representation for formulas, or with respect to the extended connection language for circuits.</p>
<p>Consequently, it is also computable by polynomial-size unbounded fan-in <span class="math-container">$\land$</span>, <span class="math-container">$\lor$</span>, <span class="math-container">$\neg$</span> circuits of depth <span class="math-container">$O(\log n/\log\log n)$</span>. This is optimal by the usual circuit lower bounds for Parity or Majority.</p>

CC BY-SA 4.0
2023-01-02T15:11:24.893Z
Thanks! It is still unclear to me the relationship between the size of the formulas and of the circuits. You wrote "bounded fan-in Boolean formulas or circuits" as if it were the same thing. Am I missing something obvious?
Nicola Gigante
CC BY-SA 4.0
2023-01-02T15:17:29.240Z
Also, would you please provide some basic references with these well known results for someone not acquainted with circuit complexity? A text-book is fine.
Nicola Gigante
CC BY-SA 4.0
2023-01-02T15:34:16.883Z
Any circuit can be unravelled to a formula of the same depth. Thus bounded fan-in Boolean formulas of depth $O(\log n)$ and bounded fan-in Boolean circuits of depth $O(\log n)$ compute the same class of languages. (This may of course increase the size, but bounded fan-in things of depth $O(\log n)$ have necessaily polynomial size anyway.)
Emil Jeřábek
CC BY-SA 4.0
2023-01-02T15:47:53.753Z
Thanks! Do you have any basic reference suitable for citing these basic results?
Nicola Gigante
CC BY-SA 4.0
2023-01-02T15:51:28.973Z
You can look at I. Wegener, *The complexity of Boolean functions*. The book is rather old (e.g., it predates the definition of TC^0 as a separate class), but it includes the construction of $O(\log n)$ depth multiplication circuits using carry-save addition as well as basic relationships between formula and circuit complexity.
Emil Jeřábek
CC BY-SA 4.0
2023-01-02T17:26:10.967Z
Thank you very much!
Nicola Gigante
CC BY-SA 4.0
2023-01-03T08:35:00.953Z
I've posted a followup question here, it would be great if you were interested in answering that as well: https://cstheory.stackexchange.com/q/52340/18101
Nicola Gigante
CC BY-SA 4.0
2023-01-02T14:47:21.780Z
2023-01-02T14:47:21.780Z
Emil Jeřábek
<p>I'd need some bounds on the size of Boolean formulas (over <span class="math-container">$\land$</span>, <span class="math-container">$\lor$</span> and <span class="math-container">$\neg$</span>) computing the multiplication of two integers.</p>
<p>I'm not an expert in circuit complexity and I'm crawling through literature. As far as I know, it's known that multiplication is not in <span class="math-container">$\mathsf{AC}^0$</span>, <em>i.e.</em> it cannot be computed by a polynomial-size circuit of constant depth, because it can be used to compute Parity.</p>
<p>But, first of all, what if I relax the restriction on depth? Can it be computed by polynomial-size circuits of, say, logarithmic depth? This would still be a polynomial-size circuit as a whole, right?</p>
<p>Then, this is for circuits, but does this tell me anything on the size of Boolean <strong>formulas</strong>? At worst, a formula can be exponentially larger than the circuit, but does it happen specifically for any formula for multiplication?</p>
<p>In other words, are there <strong>polynomial-size</strong> formulas to compute integer multiplication?</p>

<circuit-complexity>
Formula complexity of arithmetic multiplication
Nicola Gigante
# Formula complexity of arithmetic multiplication

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

I'd need some bounds on the size of Boolean formulas (over $\land$, $\lor$ and $\neg$) computing the multiplication of two integers.

I'm not an expert in circuit complexity and I'm crawling through literature. As far as I know, it's known that multiplication is not in $\mathsf{AC}^0$, *i.e.* it cannot be computed by a polynomial-size circuit of constant depth, because it can be used to compute Parity.

But, first of all, what if I relax the restriction on depth? Can it be computed by polynomial-size circuits of, say, logarithmic depth? This would still be a polynomial-size circuit as a whole, right?

Then, this is for circuits, but does this tell me anything on the size of Boolean **formulas**? At worst, a formula can be exponentially larger than the circuit, but does it happen specifically for any formula for multiplication?

In other words, are there **polynomial-size** formulas to compute integer multiplication?

**Tags:** circuit-complexity

---

## 1 answers

### Answer by username_1 on 2023-01-02. Score: 7 | Accepted answer

Multiplication is well known to be computable in uniform $\mathrm{TC}^0$, i.e., by a DLOGTIME-uniform family of constant-depth polynomial-size circuits using (unbounded fan-in) $\land$, $\lor$, $\neg$, and Majority gates. In fact, multiplication is $\mathrm{TC}^0$-complete under $\mathrm{AC}^0$ Turing reductions.

Consequently, it is also computable in uniform $\mathrm{NC}^1$, i.e., by a DLOGTIME-uniform family of bounded fan-in Boolean formulas or circuits of depth $O(\log n)$ (thus of polynomial size). Here, uniformity is with respect to the usual infix or prefix representation for formulas, or with respect to the extended connection language for circuits.

Consequently, it is also computable by polynomial-size unbounded fan-in $\land$, $\lor$, $\neg$ circuits of depth $O(\log n/\log\log n)$. This is optimal by the usual circuit lower bounds for Parity or Majority.

> **Comments:**
> **username_0**: Thanks! It is still unclear to me the relationship between the size of the formulas and of the circuits. You wrote "bounded fan-in Boolean formulas or circuits" as if it were the same thing. Am I missing something obvious?  
> **username_0**: Also, would you please provide some basic references with these well known results for someone not acquainted with circuit complexity? A text-book is fine.  
> **username_1**: Any circuit can be unravelled to a formula of the same depth. Thus bounded fan-in Boolean formulas of depth $O(\log n)$ and bounded fan-in Boolean circuits of depth $O(\log n)$ compute the same class of languages. (This may of course increase the size, but bounded fan-in things of depth $O(\log n)$ have necessaily polynomial size anyway.)  
> **username_0**: Thanks! Do you have any basic reference suitable for citing these basic results?  
> **username_1**: You can look at I. Wegener, *The complexity of Boolean functions*. The book is rather old (e.g., it predates the definition of TC^0 as a separate class), but it includes the construction of $O(\log n)$ depth multiplication circuits using carry-save addition as well as basic relationships between formula and circuit complexity.  
> **username_0**: Thank you very much!  
> **username_0**: I've posted a followup question here, it would be great if you were interested in answering that as well: https://cstheory.stackexchange.com/q/52340/18101  

---

