$\def\dlt{\mathrm{DLOGTIME}}\def\nlt{\mathrm{NLOGTIME}}\def\mr{\mathrm}$During a recent discussion on another question, I mentioned a factoid $\exists\dlt=\nlt$, but then I realized that I may have misremembered it, as I can’t recall the argument or where I’ve seen it. But anyway, I’d like to know whether it is true.
To be clear, the machine model (as usual in this context) is a multi-tape Turing machine with random-access input: i.e., the input is accessed by means of a query (index) tape; if the query tape holds number $q$ in binary, we can ask the machine to provide the $q$th bit of the input. (The query does not modify the content of the query tape, or its head position.)
For $\exists\dlt$, the existential witness is accessed through another query tape of its own. (Perhaps we could even allow an arbitrary finite number of such witness tapes; this would make $\exists\dlt$ closed under the $\exists$ operator, and $\exists\dlt=\exists\nlt$. I’m not sure what is the most natural definition here; the upper bounds below hold in the more general setting, but I’d be happy for an answer with just one witness.)
Clearly, we can simulate nondeterminism by an existential witness that records the sequence of nondeterministic choices, hence $$\nlt\subseteq\exists\dlt.$$ The question is whether the converse is true as well:
Question: Is $\exists\dlt=\nlt$? If not, is at least $\exists\dlt\subseteq\mr{NTIME}\bigl(\log n(\log\log n)^{O(1)}\bigr)$?
I can show that $$\begin{align*}\exists\dlt&\subseteq\Sigma_2\text-\mr{TIME}(\log n)\subseteq\mr{AC}^0,\\ \exists\dlt&\subseteq\mr{NTIME}\bigl((\log n)^2\bigr).\end{align*}$$ More precisely, the following holds, which implies both:
Proposition: Every $\exists\dlt$ language can be decided by a $\Sigma_2$ alternating machine that makes $O(\log n)$ existential steps and $\log\log n+O(1)$ universal steps followed by $O(\log n)$ deterministic steps.
To see this, first observe that an accepting run of the $\exists\dlt$ machine can only access $O(\log n)$ bits of the existential witness. (This is the crucial difference from $\exists\mr{coNLOGTIME}=\mr{NP}$, by the way.) We can simulate it by nondeterministically guessing the string $a=(a_0,\dots,a_{c\log n})$ of answers to witness queries made during the computation, and then running the $\dlt$ verifier.
The catch is we also need to make sure that $a$ is internally consistent: if the machine happens to ask for the same position twice, it receives the same answer each time. That is, if $q_i\in\{0,1\}^{O(\log n)}$ denotes the content of the query tape during the $i$th witness query, we have $$\forall i,j\le c\log n\:(q_i=q_j\implies a_i=a_j).\tag{$*$}$$ We can test this deterministically by trying all $O((\log n)^2)$ choices for $i,j$ and running the $O(\log n)$ simulation to determine $q_i,q_j,a_i,a_j$, in total time $O((\log n)^3)$; alternatively, we can select $i,j$ co-nondeterministically by making $2\log\log n+O(1)$ universal steps followed by the $O(\log n)$ deterministic simulation.
We can implement the test more efficiently by universally selecting only $i$, and then testing $(*)$ for all $j$ in a single $O(\log n)$-time pass as follows. We put a copy of $q_i$ on a work tape whose head mimicks the movement of the witness query tape, so that whenever we change the witness query tape, we know whether the newly written bit agrees or disagrees with $q_i$. Using this information, we can maintain on another work tape a unary counter showing the Hamming distance between $q_i$ and the current content of the witness query tape. Thus, we know when the machine makes a witness query with $q_j=q_i$, and we can check if $a_i=a_j$.
Note that we can also modify the machine so that any computation path makes at most one query to the original input, and if so, halts immediately afterwards. (This is the “Ruzzo convention”.) Indeed, we can guess answers to input queries during the nondeterministic phase of the algorithm, and then universally branch off a verification of each of them (crucially, the verification of $(*)$ does not make any new queries to the original input). Using the standard translation of alternating logarithmic time to bounded-depth circuits (cf. here), this gives:
Corollary: Every $\exists\dlt$ language is recognizable by a $\dlt$-uniform family of polynomial-size DNF circuits such that all the conjunctions have fan-in $O(\log n)$.
Some further ideas I tried that did not fare any better:
Consider the relevant part of the existential witness as a partial Boolean function $\{0,1\}^{O(\log n)}\to\{0,1\}$ with domain of size $O(\log n)$, rather than just a sequence of the query answer bits. This obviates the necessity of checking $(*)$. The simplest way to represent the partial witness is a list of all queries along with answers; this takes $O((\log n)^2)$ bits, and $O((\log n)^2)$ time to look up each answer, hence the total time is $O((\log n)^3)$.
The most efficient representation of the partial witness I know of is by an ordered decision tree with $O(\log n)$ nodes (see here); this needs $O(\log n\log\log n)$ bits to write down, and $O(\log n\log\log n)$ time to evaluate each query, leading to a nondeterministic algorithm that makes $O(\log n\log \log n)$ nondeterministic guesses followed by $O((\log n)^2\log\log n)$ deterministic steps.
Instead of checking all $O((\log n)^2)$ pairs $i,j$ in $(*)$, sort them first. That is, we consider the witness queries as (key,value) pairs $(i,q_i)$; we take the array $[0,\dots,c\log n]$ of the keys, and sort them according to the values. The array takes $O(\log n\log\log n)$ bits; the sorting can be done with $O(\log n\log\log n)$ comparisons, but each of those takes time $O(\log n)$, hence the overall time is $O((\log n)^2\log\log n)$. Alternatively, we may guess the sorted array, but then we need to verify that it is actually a permutation of the original array and that it is sorted, which again seems to require too much time.