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

  • 9
    $\begingroup$ OMG, Emil Jeřábek asked a question! $\endgroup$ – domotorp Jan 25 at 20:39
  • 5
    $\begingroup$ @domotorp I knew it was rare when I liked your comment, but then I checked and it is literally the first! $\endgroup$ – Joshua Grochow Jan 26 at 7:19
  • 1
    $\begingroup$ Hi Emil, I am thinking one could use the trick of initializing an array (which would then simulate the witness tape) in constant time. Each time a query is made, the answer is guessed nondeterministically, but we also perform a lookup up in the table to see if the witness bit has already been guessed. This idea does not seem enough though. $\endgroup$ – Kristoffer Arnsfelt Hansen Jan 26 at 13:53
  • $\begingroup$ @Kristoffer The resulting array is then the sequence of all queries along with answers, which has size $O((\log n)^2)$. Note that given a nondeterministic (or $\Sigma_2$) algorithm, you can rearrange it (without affecting the asymptotic running time) to make all nondeterministic choices ahead, and then work deterministically; in your case, the algorithm would guess the whole array of queries and answers, and use it to look up the answers. This is a form of what I wrote in the last-but-one paragraph, using an $O((\log n)^2)$ representation of the partial oracle. Perhaps I should clarify this. $\endgroup$ – Emil Jeřábek Jan 26 at 16:38
  • 1
    $\begingroup$ @domotorp I took the liberty to steal your notation for the answers, as it is indeed more suggestive. $\endgroup$ – Emil Jeřábek Jan 26 at 16:52

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.

  • 1
    $\begingroup$ Thank you, but I don't see how this would improve the running time. If you store the $q_i$'s, just the length of the array will be $O((\log n)^2)$ bits already, hence the running time will be at least as much. (Moreover, since you have to move back and forth whenever storing new queries, this sounds like it will take time $O((\log n)^3)$. But perhaps there exists some kind of more clever implementation of random access arrays on multitape Turing machines with faster access time.) $\endgroup$ – Emil Jeřábek Jan 25 at 22:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.