<p>Divisibility is decidable in uniform <span class="math-container">$\mathrm{TC}^0$</span>, hence in uniform <span class="math-container">$\mathrm{NC}^1$</span>, i.e., it has DLOGTIME-uniform Boolean formulas of size <span class="math-container">$k^{O(1)}$</span>. I'm not aware of an explicit upper bound on the exponent being given in the literature, though in principle it can be estimated by inspection of the (rather complicated) division/iterated multiplication algorithms due to Hesse, Allender, and Barrington, or even the earlier nonuniform construction by Beame, Cook, and Hoover.</p>

CC BY-SA 4.0
2024-07-27T03:00:14.107Z
Thanks, much precise as usual!
Nicola Gigante
CC BY-SA 4.0
2024-07-26T09:44:36.460Z
2024-07-26T09:44:36.460Z
Emil Jeřábek
<p>Given two <span class="math-container">$k$</span>-bits numbers <span class="math-container">$n$</span> and <span class="math-container">$m$</span>, how large is a Boolean formula that computes whether <span class="math-container">$n = 0\pmod m$</span>?</p>

<circuit-complexity>
Formula complexity of $n = 0 \pmod m$
Nicola Gigante
# Formula complexity of $n = 0 \pmod m$

(Asked by: username_0 on 2024-07-25)

Given two $k$-bits numbers $n$ and $m$, how large is a Boolean formula that computes whether $n = 0\pmod m$?

**Tags:** circuit-complexity


---

## 1 answers

### Answer by username_1 on 2024-07-26. Score: 10 | Accepted answer

Divisibility is decidable in uniform $\mathrm{TC}^0$, hence in uniform $\mathrm{NC}^1$, i.e., it has DLOGTIME-uniform Boolean formulas of size $k^{O(1)}$. I'm not aware of an explicit upper bound on the exponent being given in the literature, though in principle it can be estimated by inspection of the (rather complicated) division/iterated multiplication algorithms due to Hesse, Allender, and Barrington, or even the earlier nonuniform construction by Beame, Cook, and Hoover.

> **Comments:**
> **username_0**: Thanks, much precise as usual!  

---

