1
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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)).$$ $\endgroup$
    – Emil Jeřábek
    Oct 23, 2020 at 6:58
  • 1
    $\begingroup$ 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 ... $\endgroup$
    – Emil Jeřábek
    Oct 23, 2020 at 7:17
  • $\begingroup$ ... while multiplication (and primality) are presumably not computable in deterministic linear time, they are computable in the linear-time hierarchy. $\endgroup$
    – Emil Jeřábek
    Oct 23, 2020 at 7:18
  • $\begingroup$ 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$. $\endgroup$
    – Emil Jeřábek
    Oct 23, 2020 at 7:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.