# How to show that the product of two binary numbers can be determined in AC1?

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.
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
• AC$^1$ with bounded fan-in is known as NC$^1$. – Yuval Filmus Jun 29 at 15:53