<p>See <a href="ftp://athos.rutgers.edu/cs/pub/allender/division.eatcs.pdf" rel="nofollow">Eric Allender's survey</a> of "recent" breakthroughs (circa more than a decade ago) in the complexity of division. The bottom line is that </p>

<blockquote>
  <p>Division is complete for DLOGTIME-uniform $\mathsf{TC}^0$</p>
</blockquote>

<p>so in particular there is a poly-sized circuit (of constant depth) that takes $x$ and $y$ as input and produces $x/y$. Notice that this circuit doesn't even need to be arithmetic (it only needs MAJORITY gates in addition to boolean gates)</p>

CC BY-SA 3.0
2014-04-11T06:57:22.750Z
2014-04-11T06:57:22.750Z
Suresh Venkat
<p>Can we perform integer division with a polynomial size arithmetic circuit over $\mathbb{Q}$ that takes as input the numerator and denominator? </p>

CC BY-SA 3.0
2014-04-11T07:32:00.013Z
By arithmetic circuit do you mean a circuit composed of addition and multiplication gates?
Kaveh
<arithmetic-circuits>
Can a polynomial sized arithmetic ciruits perform integer division?
guest23
# Can a polynomial sized arithmetic ciruits perform integer division?

(Asked by: username_0 on 2014-04-11)

Can we perform integer division with a polynomial size arithmetic circuit over $\mathbb{Q}$ that takes as input the numerator and denominator?

**Tags:** arithmetic-circuits

> **Comments:**
> **username_1**: By arithmetic circuit do you mean a circuit composed of addition and multiplication gates?  

---

## 1 answers

### Answer by username_2 on 2014-04-11. Score: 4

See [Eric Allender's survey](ftp://athos.rutgers.edu/cs/pub/allender/division.eatcs.pdf) of "recent" breakthroughs (circa more than a decade ago) in the complexity of division. The bottom line is that

> Division is complete for DLOGTIME-uniform $\mathsf{TC}^0$

so in particular there is a poly-sized circuit (of constant depth) that takes $x$ and $y$ as input and produces $x/y$. Notice that this circuit doesn't even need to be arithmetic (it only needs MAJORITY gates in addition to boolean gates)


---

