Uniformity Within Parameterized Circuit Classes

In [14], Ruzzo introduced uniformity conditions for shallow circuit classes. The following definition is based on Ruzzo’s $U_D$-uniformity.¹¹1Ruzzo requires $\mathrm{𝖣𝖳𝖨𝖬𝖤}(\log s(n))$ on a slightly different language, but this is equivalent for our cases.

That is, a deterministic multitape Turing machine can decide $w\in L_{BD}(C)$ in time $O(|w|)$.

Later uniformity notions were based on random-access Turing machines. A random-access Turing machine [16, Appendix A4] is a multitape Turing machine equipped with a special query tape and query state. Whenever the machine enters the query state, it obtains the value of the $a$th bit on the input tape, where $a$ is the binary address written on the query tape, or an out-of-bounds response if $a$ is beyond the length of the input (or not a number). Importantly, the query tape is not erased on query, and the input tape is read-only.

We write ${\mathrm{𝖣𝖳𝖨𝖬𝖤}}^{𝖱}(t(n))$ for the class of problems that can be solved in $O(t(n))$ time by a random-access Turing machine, and define ${\mathrm{𝖣𝖳𝖨𝖬𝖤}}^{𝖱}(t(n)+f(k))$ analogously to Definition 3.

Logtime-D-uniformity is arguably the most well-known uniformity condition for ${\mathrm{𝖠𝖢}}^0$. Yet not much is known about ${\mathrm{𝖣𝖳𝖨𝖬𝖤}}^{𝖱}(\log n)$. Clearly ${\mathrm{𝖣𝖳𝖨𝖬𝖤}}^{𝖱}(\log n)\subseteq \mathrm{𝖣𝖳𝖨𝖬𝖤}(n\log n)$ [13], but it is to the best of our knowledge unknown whether this is strict. As far as we know, it is for example also open whether a random-access Turing machine can multiply two $m$-bit numbers in $O(m)$ time. What is known is that they can add $m$-bit numbers in $O(m)$ time, and determine the length of their input in $O(\log n)$ time [11, Lemma 6.1].

The class $\mathrm{𝖥𝖮}$ consists of the languages that are first-order definable in the predicates $\le$ and $\mathrm{Bit}$. That is, they are defined by a first-order sentence using symbols from $\{\forall ,\wedge ,\neg ,\le ,\mathrm{Bit},X\}$ as follows [11, 9]. A word $w$ induces a first-order structure $S_w$ whose domain consists of the numbers 0 to $|w|$, where: $\le$ is interpreted as the standard order on natural numbers, $\mathrm{Bit}(i,j)$ is true if and only if the $i$th bit of $j$ is 1, and $X(i)$ is true if and only if the $i$th bit of $w$ is 1. A sentence $\varphi$ then defines the language $\{w:S_w\vDash \varphi \}$.

We may assume that the language also contains ternary predicates for addition and multiplication, as they are first-order definable in $\le$ and $\mathrm{Bit}$ [11, 9]. We may also assume that it contains a constant symbol for the length of the input, and that we may quantify over (the binary representations of) numbers below $O({|w|}^c)$, by using $O(c)$ variables [11, p. 293].

For polynomially-sized circuit families, it can be shown that linear-BD-uniformity implies logtime-D-uniformity, which in turn implies $\mathrm{𝖥𝖮}$-D-uniformity. $\mathrm{𝖥𝖮}$-D-uniformity is easier to work with than logtime-D-uniformity. In fact, there are many examples of languages for which the natural circuit families deciding them are quickly seen to be $\mathrm{𝖥𝖮}$-D-uniform, but for which it is unknown whether they are logtime-D-uniform or linear-BD-uniform.

It suffices to define an admissible numbering for $D=A[B/M]$, and show that, under this numbering, $(L_{BD}(D),{\pi }_4)$ is in $\mathrm{𝖣𝖳𝖨𝖬𝖤}(n+f(k))$ for some computable $f$.

Give unmarked internal gates $G$ in $A_{n,k}$ number $⟨0,G⟩$ in $D_{n,k}$. If $G$ is a marked gate and $G^{\prime }$ is a gate in the circuit $B_{\mathrm{In}(G,n,k),k}$ replacing it, number it $⟨G,G^{\prime }⟩$ in $D_{n,k}$. This numbering based on admissible numberings of $A$ and $B$ leads to an admissible numbering of $D$ (cf. Definition 5). An $O(n+f(k))$-time algorithm deciding $(L_{BD}(D),{\pi }_4)$ is then obtained from $M$, $\mathrm{In}$, and $O(n+g(k))$-time algorithms for $L_{BD}(A)$ and $L_{BD}(B)$ witnessing the linear-BD-uniformity of $A$ and $B$. A full proof can be found in the full version (Appendix B). $◀$

We do not know whether the logtime-D-uniform (parameterized) circuit families are closed under substitution, for reasonable assumptions on $M$ and $\mathrm{In}$. It appears that two random-access Turing machines $P,Q$ are not easily composed without a runtime overhead. For example, computing $P(x_r)$ on input $x=⟨x_l,x_r⟩$ seems to require offsetting each query that $P$ makes by an $O(|x_l|)$ offset which, if done naively, adds an $O(\log |x_l|)$ overhead to every query. These naive combinations of two logtime random-access Turing machines can result in $\mathrm{\Omega }({(\log n)}^2)$-time random-access Turing machines, instead of logtime.

Let $a$ be a constant and $h$ a computable function so that for all $n,k$ we have that $N(n,k)=2^{a\log n+h(k)}$ is greater than any gate number in $C_{n,k}$ (cf. Definition 5). Then the binary representation of $N(n,k)$ is computable in $O(\log n+g(k))$ time without random access for some computable $g$.

We describe a linear-BD-uniform circuit family $D$ equivalent with $C$. Circuit $D_{n,k}$ consists of its input gates, $d(k)$ layers of $N(n,k)$ subcircuits we call simgates, and one final subcircuit that forwards the correct simgate to the output gate. Every simgate of layer $m+1$ takes all simgates of layer $m$ as input, together with the input gates. We number the $q$th simgate in layer $m$ with $⟨m,q⟩$, and the idea is that simgate $⟨m,q⟩$ in $D_{n,k}$ approaches (monotonically) gate $q$ in $C_{n,k}$, so that, by layer $d(k)$, simgate $⟨d(k),q⟩$ correctly simulates gate $q$ in $C_{n,k}$.

See Figure 3 for the internals of a simgate. In order to approach gate $q$ of $C_{n,k}$, simgate $⟨m,q⟩$ queries $L_D(C)$ to select the simgates $⟨m-1,p⟩$ where $p$ feeds into $q$ in $C_{n,k}$, and the input gates $m$ where input gate $m$ feeds into $q$ in $C_{n,k}$. It also queries $L_D(C)$ to determine whether $q$ is an and, or, or not gate, and simulates that action on its selected inputs. (By our construction in Figure 3, if is not a gate in $C_{n,k}$ then simgate $⟨m,q⟩$ outputs 0, but it has no influence on the output of $D_{n,k}$, because it is never selected.)

Assume for now that components of simgates can directly answer membership queries for $L_D(C)$. In this case the construction shows that they select their input as described above, and perform the action of $q$ (if $q$ is a gate in $C_{n,k}$). Then by induction, for every gate $q$ in $C_{n,k}$, the simgate $⟨d(k),q⟩$ in the final layer will have the same output as $q$.

To see this, first observe that by our assumption, the output of $⟨m+1,q⟩$ is the same as that of $q$ if for all internal gates $p$ that feed into $q$, the output of $⟨m,p⟩$ is equal to that of $p$. Define the level of a gate to be the length of the longest path from it to an input gate. The output of simgates $⟨m,q⟩$ is the same as that of $q$ if the level of $q$ is below $m$. This can be shown by induction based on the following: (1) If $q$ has level 1 in $C_{n,k}$, then $q$ only takes input gates, and by our observation simgates $⟨m,q⟩$ have the same output as $q$ for all $m\ge 1$. (2) If $q$ has level $m+1$ and simgates $⟨m^{\prime },p⟩$ have the same output as $p$ for all $p$ of lower level and $m^{\prime }\ge m$, then by our observation $⟨m^{\prime \prime },q⟩$ has the same output as $q$ for all $m^{\prime \prime }\ge m+1$.

Finally, to make $D_{n,k}$ behave as desired, it should feed into the output gate the output of simgate $⟨d(k),q⟩$ for the gate $q$ that feeds into the output gate in $C_{n,k}$. This is the role of the final subcircuit mentioned at the start of the proof. It takes all simgates in the final layer as input, and queries $L_D(C)$ to propagate the output of the correct $⟨d(k),q⟩$.

The circuits $D_{n,k}$ have very regular structure. Each $D_{n,k}$ is essentially a matrix of $d(k)$ layers of $N(n,k)$ simgates, and each simgate gets all the simgates of the previous layer as input together with the input gates. Apart from the rounded query blocks, the internals of the simgates are also easily seen to be linear-BD-uniform, using for example the admissible numbering in Figure 3. It remains to show how the queries in the simgates are implemented.

The $L_D(C)$ queries represented by the dashed query blocks in Figure 3 can be implemented by plugging in linear-BD-uniform circuits for $L_D(C)$. A constant-depth linear-BD-uniform circuit family $E$ deciding $L_D(C)$ exists by Lemma 19, and its circuits can be substituted in linear-BD-uniformly by 23. It is left to prove that the circuits can be given the appropriate query inputs in a linear-BD-uniform way.

For now, we work with the circuit family $D^{\prime }$ in which the circuits of $E$ have not yet been substituted. Here gates $⟨m,q,4⟩$ (cf. Figure 3) are just and gates that will be replaced with circuits from $E$ later to obtain $D$ from $D^{\prime }$. We add constant circuits $V_0$ and $V_1$ to every $D_{n,k}^{\prime }$, where $V_0$ has the constant output 0, and $V_1$ is constant 1. The circuit of $E$ replacing $⟨m,q,4⟩$ should decide whether gate $q$ in $C_{n,k}$ is an or gate. This can be achieved by giving gate $⟨m,q,4⟩$ the input $I=⟨q,1,ϵ,1^n,1^k⟩$. That is, in terms of connection languages, we want $w=⟨⟨m,q,4⟩,V_b,i,n,k⟩\in L_{BD}(D^{\prime })$ if and only if the $i$th bit of $I$ is $b$. It can be verified that, given such $w$, the $i$th bit of $I$ can be decided in time $|w|+g(k)$ for some computable $g$, and so these queries can be answered in time $|w|+g(k)$ as required for linear-BD-uniformity.

This addresses the type-queries in the simgates. The other queries, those asking whether (input) gate $p$ feeds into $q$ in $C_{n,k}$, are handled similarly, with a small complication: checking whether $p$ feeds into $q$ can be reduced to checking whether $p$ is the $i$th input of $q$ for any $i\le N(n,k)$, so the dashed blocks in Figure 3 corresponding to this type of query are actually or gates over $N(n,k)$ gates that will be substituted by circuits of $E$, where the $i$th gate will be given an $L_D(C)$-query to determine whether $p$ is the $i$th input of $q$.

In summary: the queries in the simgates are implemented by hard-wiring $L_D(C)$-queries into the query blocks in a linear-BD-uniform manner, and then substituting in a linear-BD-uniform circuit family $E$ that decides $L_D(C)$ to answer them. The resulting circuit family $D$ is linear-BD-uniform by Lemma 23, and is equivalent with $C$ by design. $◀$

Theorem 12 (mentioned in Section 2.5) can be proved similarly. Using simgates, we can now also prove the following.

By the $\mathrm{𝖥𝖮}$-D-uniformity of $C$, we have $(L_D(C),{\pi }_4)\in \mathrm{Para}(\mathrm{𝖥𝖮})$. Theorem 11 gives that $(L_D(C),{\pi }_4)$ is in $\mathrm{Para}(\text{logtime-D-uniform }{\mathrm{𝖠𝖢}}^0)$, which by Theorem 14 is equal to logtime-D-uniform $\text{para-}{\mathrm{𝖠𝖢}}^0$. Hence, by 24, $(L_D(C),{\pi }_4)$ is in linear-BD-uniform $\text{para-}{\mathrm{𝖠𝖢}}^0$. The rest of the proof is now the same as for Lemma 24, using a simgate-construction of $d(k)$ layers, and answering $L_D(C)$-queries in the simgates by substituting in a family witnessing that $(L_D(C),{\pi }_4)$ is in linear-BD-uniform $\text{para-}{\mathrm{𝖠𝖢}}^0$. $◀$

We have now proved our main result.

For both $\text{para-}{\mathrm{𝖠𝖢}}^0$ and $\text{para-}{\mathrm{𝖠𝖢}}^{0\uparrow }$, Item (1) implies Item (2) by Lemma 18, and (2) implies (3) by Lemma 20. Finally, Item (3) implies Item (1) by 25. (For $\text{para-}{\mathrm{𝖠𝖢}}^0$, the last implication is obtained from Lemma 25 by setting $d(k)=O(1)$.) $◀$

We can also observe the following, which suggests that $\mathrm{𝖥𝖮}$-D-uniformity is not too coarse for $\text{para-}{\mathrm{𝖠𝖢}}^{0\uparrow }$. (This mirrors that ($\mathrm{𝖥𝖮}$-uniform ${\mathrm{𝖠𝖢}}^0$)-uniform ${\mathrm{𝖠𝖢}}^0$ equals $\mathrm{𝖥𝖮}$-uniform ${\mathrm{𝖠𝖢}}^0$.)

If $(L_D(C),{\pi }_4)$ is in $\mathrm{𝖥𝖮}$-uniform $\text{para-}{\mathrm{𝖠𝖢}}^{0\uparrow }$, then by Theorem 21 it lies in linear-BD-uniform $\text{para-}{\mathrm{𝖠𝖢}}^{0\uparrow }$. Follow the proof of Lemma 24, now using linear-BD-uniform $\text{para-}{\mathrm{𝖠𝖢}}^{0\uparrow }$-families for the query blocks. $◀$