Is there a fine grained relation between LH and AC0?

Question

The wikipedia article states that the Logarithmic time hierarchy (LH) is equal to FO-uniform AC⁰. But since the natural way to think about LH is in terms of its levels (with DLogTime at the zeroth level, NLogTime and coNLogTime at the first level, and the log-time machines with (k-1)-alternations at the k-th level), it is natural to wonder whether there is a fine grained relation between the classes from the individual levels like (coNLogTime) with specific subclasses of AC⁰.

Answer 1

Here are the definitions that make it work. Fix $d\ge1$:

• Let $\Sigma_d\text-\mathrm{TIME}(f(n))$ denote the set of languages recognizable in time $O(f(n))$ by an alternating Turing machine that starts in an existential state, and makes at most $d-1$ alternations. Since we are interested in logarithmic time, we work in a model where we do not have an input tape, but we can access the input by writing on a query tape the index of an input position in binary, and its assumed value, and asking the input oracle if our assumption is correct. Additionally, we require that the ATM makes only one such query, at the very end of the computation, and returns the answer of the oracle as the result of the computation. (In order to make this feasible, we need to stipulate that the machine starts with the input length $n$ written in binary on one of its tapes. A log-time TM can compute the length of its input, but it needs $\Omega(\log n)$ input queries to do that.)

• A Boolean formula or circuit is $\Sigma_d$ if it consists of $d$ alternating layers of (unbounded fan-in) conjunctions and disjunctions, the top layer being a disjunction, and a layer of literals (variables and negated variables) at the bottom. A language is in non-uniform $\Sigma_d\text-\mathrm{AC}^0$ if it is computable by a family of polynomial-size $\Sigma_d$ circuits $\{C_n:n\in\mathbb N\}$. A language is in DLOGTIME-uniform $\Sigma_d\text-\mathrm{AC}^0$ if, additionally, we can enumerate the nodes of $C_n$ by numbers of $O(\log n)$ bits in such a way that we can compute the following in (deterministic) time $O(\log n)$:

  • Given $n$ and $u$, check if $u$ is the output node of $C_n$.

  • Given $n$ and $u$, find the type ($\land$, $\lor$, variable, negated variable) of node $u$ in $C_n$.

  • Given $n$, $u$, and $v$, determine if there is a wire from node $v$ to $u$ in $C_n$, or if $u$ denotes variable number $v$ or its negation.

Proposition: For any $d\ge1$, $\Sigma_d\text-\mathrm{TIME}(\log n)$ equals DLOGTIME-uniform $\Sigma_d\text-\mathrm{AC}^0$.

Note that the definition of DLOGTIME uniformity above refers to more-or-less the standard direct connection language of the circuit. It is not sensitive to minor changes in the definition.

On the other hand, the restriction to input queries only at the end in the definition of $\Sigma_d\text-\mathrm{TIME}(\log n)$ does appear to be significant. I cannot exactly characterize the class without this restriction, but it is somewhere between DLOGTIME-uniform $\Sigma_d\text-\mathrm{AC}^0$ and $\Sigma_{d+\frac12}\text-\mathrm{AC}^0$, where a $\Sigma_{d+\frac12}$-circuit is a $\Sigma_{d+1}$-circuit whose bottom layer only allows connectives of fan-in $O(\log n)$.

The proof of the proposition is fairly straightforward.

On the one hand, a language described by a DLOGTIME-uniform family of $\Sigma_d$ circuits can be evaluated by an ATM in a top-down fashion: in the initial existential state, we guess (and check) the top node of the circuit, which is a disjunction, and nondeterministically choose one of its input conjunction nodes. We switch to a universal state, and co-non-deterministically choose the next node. We proceed this way down the circuit. At the bottom layer of connectives, we (existentially or universally, as appropriate) choose not only the next node, which is a literal, but also its type ($x_v$ or $\neg x_v$). Then we make an input query to find the value of the literal, and return it.

On the other hand, consider a language computable by a $\Sigma_d\text-\mathrm{TIME}(\log n)$ machine. We may assume that as the machine computes, it records a log of the states it has been in (which in particular tells us if it is in an existential or universal state, how many alternations it went through, and which nondeterministic choices it has taken). Let $C_n$ be the circuit whose nodes are certain configurations of the ATM on inputs of $n$ bits, namely: the initial configuration; the final query configurations; and configurations just after an alternation between existential and universal states. The type of a non-final node is $\lor$ or $\land$ according to if the corresponding configuration is existential or universal. There is a wire from $v$ to $u$ if there is an alternation-free computation path from $u$ to $v$; note that this computation path is uniquely determined by $v$’s log, hence it can be checked in DLOGTIME.