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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – gigabytes
    Jan 2 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$
    – gigabytes
    Jan 2 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$
    – Emil Jeřábek
    Jan 2 at 15:34
  • $\begingroup$ Thanks! Do you have any basic reference suitable for citing these basic results? $\endgroup$
    – gigabytes
    Jan 2 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$
    – Emil Jeřábek
    Jan 2 at 15:51

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.

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