5
$\begingroup$

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?

$\endgroup$

1 Answer 1

7
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$ Commented Jan 2, 2023 at 15:11
  • $\begingroup$ 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. $\endgroup$ Commented Jan 2, 2023 at 15:17
  • $\begingroup$ 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.) $\endgroup$ Commented Jan 2, 2023 at 15:34
  • $\begingroup$ Thanks! Do you have any basic reference suitable for citing these basic results? $\endgroup$ Commented Jan 2, 2023 at 15:47
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 2, 2023 at 15:51

Your Answer

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

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