<p>I’ve been reading up on the connection between first order logic and small circuit complexity classes, and specifically Barrington, Immerman, and Straubing’s paper “On Uniformity Within <span class="math-container">$\mathit{NC}^1$</span>”, where they prove <span class="math-container">$\mathit{DLOGTIME}$</span>-uniform <span class="math-container">$\mathit{AC}^0$</span> = <span class="math-container">$\mathit{FO}[+,\times]$</span>. However, it seems to me that <span class="math-container">$\mathit{FO}[+,\times]$</span> is much more powerful than <span class="math-container">$\mathit{DLOGTIME}$</span>-uniform <span class="math-container">$\mathit{AC}^0$</span>. For example, the following sentence:</p>
<p><span class="math-container">$$
\forall x \,(Qx \lor \exists a \exists b \,(a\times b = x \land a\ne1 \land b\ne1))
$$</span></p>
<p>can be implemented as a circuit as an <span class="math-container">$\mathrm{AND}$</span> gate that is only connected to prime-numbered inputs (including input 1), and so defines the language <span class="math-container">$\{1, 11, 110, 1100, 11001, 110010\}$</span>. However, <span class="math-container">$\mathit{DLOGTIME}$</span> only has time linear in the size of the gate indices to determine whether a connection exists between two gates. It seems to me that to recognize the connectivity language in linear time, one would have to be able to tell whether or not the input gate index was prime, and <span class="math-container">$\mathrm{PRIMES}$</span>, although in <span class="math-container">$P$</span>, is not computable in linear time. How can this language be <span class="math-container">$\mathit{DLOGTIME}$</span>-uniform <span class="math-container">$\mathit{AC}^0$</span> then?</p>

CC BY-SA 4.0
2020-10-23T06:58:25.627Z
Your sentence is equivalent to $\forall x\,Qx$, as you can always satisfy the disjunction by taking $a=1$ for the existential quantifier. Based on your description in words, you probably intended the sentence to read $$\forall x\,((\forall a\,\forall b\,(a\cdot b=x\to a=1\lor b=1))\to Qx),$$ or equivalently, $$\forall x\,(Qx\lor\exists a\,\exists b\,(a\cdot b=x\land a\ne1\land b\ne1)).$$
Emil Jeřábek
CC BY-SA 4.0
2020-10-23T07:17:36.620Z
Anyway, the root of your confusion is that you are prematurely eliminating connectives, making the circuit *harder* to describe. Just translate the quantifiers literally to propositional logic: you get an AND over all $x=0,\dots,n-1$ of binary ORs of $Q_x$ with ORs over all $a=0,\dots,n-1$ and $b=0,\dots,n-1$ of ANDs of constant $0/1$ circuits depending on if $ab=x$, $a\ne1$, or $b\ne1$. Thus, you don’t need a linear-time algorithm for *primality*, but only for the *graph of multiplication*. You still can’t do that, but you can fix it by adding more ANDs and ORs; the point is that ...
Emil Jeřábek
CC BY-SA 4.0
2020-10-23T07:18:48.203Z
... while multiplication (and primality) are presumably not computable in deterministic linear time, they are computable in the *linear-time hierarchy*.
Emil Jeřábek
CC BY-SA 4.0
2020-10-23T07:43:55.333Z
Also, you are confusing the terms. You are not talking about $FO[+,\times]$-uniform anything, you are talking about just $FO[+,\times]$ itself. The statement is that the class $FO[+,\times]$ coincides with the DLOGTIME-uniform class $AC^0$.
Emil Jeřábek
<lo.logic><uniformity><ac0>
$\mathit{FO}[+,\times]$ seems more powerful than $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$?
Jake
# $\mathit{FO}[+,\times]$ seems more powerful than $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$?

(Asked by: username_0 on 2020-10-23)

I’ve been reading up on the connection between first order logic and small circuit complexity classes, and specifically Barrington, Immerman, and Straubing’s paper “On Uniformity Within $\mathit{NC}^1$”, where they prove $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$ = $\mathit{FO}[+,\times]$. However, it seems to me that $\mathit{FO}[+,\times]$ is much more powerful than $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$. For example, the following sentence:

$$
\forall x \,(Qx \lor \exists a \exists b \,(a\times b = x \land a\ne1 \land b\ne1))
$$

can be implemented as a circuit as an $\mathrm{AND}$ gate that is only connected to prime-numbered inputs (including input 1), and so defines the language $\{1, 11, 110, 1100, 11001, 110010\}$. However, $\mathit{DLOGTIME}$ only has time linear in the size of the gate indices to determine whether a connection exists between two gates. It seems to me that to recognize the connectivity language in linear time, one would have to be able to tell whether or not the input gate index was prime, and $\mathrm{PRIMES}$, although in $P$, is not computable in linear time. How can this language be $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$ then?

**Tags:** lo.logic, uniformity, ac0
> **Comments:**
> **username_1**: Your sentence is equivalent to $\forall x\,Qx$, as you can always satisfy the disjunction by taking $a=1$ for the existential quantifier. Based on your description in words, you probably intended the sentence to read $$\forall x\,((\forall a\,\forall b\,(a\cdot b=x\to a=1\lor b=1))\to Qx),$$ or equivalently, $$\forall x\,(Qx\lor\exists a\,\exists b\,(a\cdot b=x\land a\ne1\land b\ne1)).$$  
> **username_1**: Anyway, the root of your confusion is that you are prematurely eliminating connectives, making the circuit *harder* to describe. Just translate the quantifiers literally to propositional logic: you get an AND over all $x=0,\dots,n-1$ of binary ORs of $Q_x$ with ORs over all $a=0,\dots,n-1$ and $b=0,\dots,n-1$ of ANDs of constant $0/1$ circuits depending on if $ab=x$, $a\ne1$, or $b\ne1$. Thus, you don’t need a linear-time algorithm for *primality*, but only for the *graph of multiplication*. You still can’t do that, but you can fix it by adding more ANDs and ORs; the point is that ...  
> **username_1**: ... while multiplication (and primality) are presumably not computable in deterministic linear time, they are computable in the *linear-time hierarchy*.  
> **username_1**: Also, you are confusing the terms. You are not talking about $FO[+,\times]$-uniform anything, you are talking about just $FO[+,\times]$ itself. The statement is that the class $FO[+,\times]$ coincides with the DLOGTIME-uniform class $AC^0$.  

---

## 0 answers

