I was working on a proof to determine that a product cannot be done in AC0, how can a proof that can be done in AC1?


Multiplication can be done even with stronger restrictions, like $AC^1$ with bounded fan-in.

Proof is little hard to typeset here, but I will outline the sketch and give a link.

  1. You shall prove, that addition of two m-bit numbers have $O(m)$ size and constant depth circuit and thus is in $AC^0$. This is pretty simple (start with looking for $O(m)$ depth and then simplify)
  2. Then you need to generalize this result to addition of many m-bit numbers and show that it have logarithmic depth and thus in $AC^1$
  3. And finally what you are looking for (product in $AC^1$) is simple corollary

Look into those lecture notes for example, where this proof is done in great details.

| cite | improve this answer | |
  • $\begingroup$ AC$^1$ with bounded fan-in is known as NC$^1$. $\endgroup$ – Yuval Filmus Jun 29 '19 at 15:53
  • $\begingroup$ @YuvalFilmus of course. If you read linked paper, it have this and many more definitions. I just tried not to overcomplicate things here. $\endgroup$ – Konstantin Vladimirov Jun 29 '19 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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