NLOGTIME versus $\exists$DLOGTIME

Question

$\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.

Answer 1

Yes, at least if we either allow $\log n \log^{O(1)} \! \log n$ time, or $O(\log n)$ queries (input, '∃' tapes, and nondeterminism) with $\log n \log^{O(1)} \! \log n$ other computation time.

A given Logtime computation path has $O(\log n)$ single-bit interactions with the query tape(s); and as you note, to answer the question, it suffices to be able to (nondeterministically) efficiently verify that a given putative computation path is self-consistent. To do that, we choose an appropriate hash function (below) converting locations on the query tapes into long-enough $O(\log \log n)$ bit numbers. For each point in the computation, and each simulated query binary tape, store the sum of hashes of locations with 1 on the tape (the sum has $O(\log \log n)$ bits), and whether the query output is 0 or 1. Verify that for each sum, the query output is constant.

Because the operations are single-bit, the sums can be updated efficiently, with $\log^{O(1)} \! \log n$ update time. Also, a 'bad' hash function will not cause false claims of consistency, so we can nondeterministically choose a function; a random one will work with high probability. We can actually select a function using just $O(\log \log n)$ random or nondeterministic bits; for example, assign the ith cell on the query tape value $2^i$, and compute everything modulo $p$ for a random prime $p$ with a large enough $O(\log \log n)$ number of bits.

Answer 2

Below is a solution that might work in the RAM model instead of Turing-machines, for which it fails (see comment by Emil).

Consider the following modification of the sorting strategy. The nondet algorithm guesses how many different queries it will make; denote this by $m=O(\log n)$. Suppose that the queried positions will be $q_1<q_2<\dots<q_m$. Note that this is not necessarily the order in which they are queried. The nondet alg first creates an empty array of length $m$, and every time it makes a query $q_i$, it guesses $i$, i.e., the position of the query in the sorted list of queries, and it stores $(q_i,a_i)$ to position $i$. Unless $i$ is already taken, in which case it verifies that the current query is the same as the stored one, and reads out the answer. After the run terminates, it passes through the array once to check that the $q_i$ are indeed sorted.