<p>Yes, at least if we either allow <span class="math-container">$\log n \log^{O(1)} \! \log n$</span> time, or <span class="math-container">$O(\log n)$</span> queries (input, '∃' tapes, and nondeterminism) with <span class="math-container">$\log n \log^{O(1)} \! \log n$</span> other computation time.</p>
<p>A given Logtime computation path has <span class="math-container">$O(\log n)$</span> 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 <span class="math-container">$O(\log \log n)$</span> 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 <span class="math-container">$O(\log \log n)$</span> bits), and whether the query output is 0 or 1.  Verify that for each sum, the query output is constant.</p>
<p>Because the operations are single-bit, the sums can be updated efficiently, with <span class="math-container">$\log^{O(1)} \! \log n$</span> 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 <span class="math-container">$O(\log \log n)$</span> random or nondeterministic bits; for example, assign the <i>i</i>th cell on the query tape value <span class="math-container">$2^i$</span>, and compute everything modulo <span class="math-container">$p$</span> for a random prime <span class="math-container">$p$</span> with a large enough <span class="math-container">$O(\log \log n)$</span> number of bits.</p>

CC BY-SA 4.0
2021-07-01T13:52:38.617Z
I was confused at first by the sums, but now I get it. The idea is to use a hashing function to compress the $O(\log n)$ witness queries of length $O(\log n)$ to length $O(\log\log n)$ each. The crucial thing is that this can be done in such a way that a single-bit update of the query tape can be simulated in time $O(\log\log n)$ rather than $O(\log n)$. This can be accomplished e.g. by taking the query value modulo a fixed $O(\log\log n)$-bit number $p$ for the hash function: updating the hash then amounts to addition or subtraction mod $p$. The consistency of the list of query hashes and ...
Emil Jeřábek
CC BY-SA 4.0
2021-07-01T13:58:02.123Z
... the corresponding replies can be checked by sorting the list. By my reckoning, all this can be implemented by nondeterministically guessing $O(\log n)$ bits, followed by $O(\log n(\log\log n)^2)$-time deterministic computation. Well done! I am still interested if the time can be brought all the way down to $O(\log n)$.
Emil Jeřábek
CC BY-SA 4.0
2021-06-30T16:16:45.187Z
2021-06-30T16:16:45.187Z
Dmytro Taranovsky
<p>Below is a solution that might work in the RAM model instead of Turing-machines, for which it fails (see comment by Emil).</p>
<p>Consider the following modification of the sorting strategy. The nondet algorithm guesses how many different queries it will make; denote this by <span class="math-container">$m=O(\log n)$</span>. Suppose that the queried positions will be <span class="math-container">$q_1&lt;q_2&lt;\dots&lt;q_m$</span>. Note that this is <em>not</em> necessarily the order in which they are queried. The nondet alg first creates an empty array of length <span class="math-container">$m$</span>, and every time it makes a query <span class="math-container">$q_i$</span>, it guesses <span class="math-container">$i$</span>, i.e., the position of the query in the sorted list of queries, and it stores <span class="math-container">$(q_i,a_i)$</span> to position <span class="math-container">$i$</span>. Unless <span class="math-container">$i$</span> 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 <span class="math-container">$q_i$</span> are indeed sorted.</p>

CC BY-SA 4.0
2021-01-25T22:45:27.847Z
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.)
Emil Jeřábek
CC BY-SA 4.0
2021-01-25T21:19:21.770Z
2021-01-26T19:04:53.253Z
2021-01-26T19:04:53.253Z
domotorp
<p><span class="math-container">$\def\dlt{\mathrm{DLOGTIME}}\def\nlt{\mathrm{NLOGTIME}}\def\mr{\mathrm}$</span>During a recent discussion on another question, I mentioned a factoid <span class="math-container">$\exists\dlt=\nlt$</span>, 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.</p>
<p>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 <span class="math-container">$q$</span> in binary, we can ask the machine to provide the <span class="math-container">$q$</span>th bit of the input. (The query does not modify the content of the query tape, or its head position.)</p>
<p>For <span class="math-container">$\exists\dlt$</span>, 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 <span class="math-container">$\exists\dlt$</span> closed under the <span class="math-container">$\exists$</span> operator, and <span class="math-container">$\exists\dlt=\exists\nlt$</span>. 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.)</p>
<p>Clearly, we can simulate nondeterminism by an existential witness that records the sequence of nondeterministic choices, hence
<span class="math-container">$$\nlt\subseteq\exists\dlt.$$</span>
The question is whether the converse is true as well:</p>
<blockquote>
<p><strong>Question:</strong> Is <span class="math-container">$\exists\dlt=\nlt$</span>? If not, is at least <span class="math-container">$\exists\dlt\subseteq\mr{NTIME}\bigl(\log n(\log\log n)^{O(1)}\bigr)$</span>?</p>
</blockquote>
<p>I can show that
<span class="math-container">$$\begin{align*}\exists\dlt&amp;\subseteq\Sigma_2\text-\mr{TIME}(\log n)\subseteq\mr{AC}^0,\\
\exists\dlt&amp;\subseteq\mr{NTIME}\bigl((\log n)^2\bigr).\end{align*}$$</span>
More precisely, the following holds, which implies both:</p>
<blockquote>
<p><strong>Proposition:</strong> Every <span class="math-container">$\exists\dlt$</span> language can be decided by a <span class="math-container">$\Sigma_2$</span> alternating machine that makes <span class="math-container">$O(\log n)$</span> existential steps and <span class="math-container">$\log\log n+O(1)$</span> universal steps followed by <span class="math-container">$O(\log n)$</span> deterministic steps.</p>
</blockquote>
<p>To see this, first observe that an accepting run of the <span class="math-container">$\exists\dlt$</span> machine can only access <span class="math-container">$O(\log n)$</span> bits of the existential witness. (This is the crucial difference from <span class="math-container">$\exists\mr{coNLOGTIME}=\mr{NP}$</span>, by the way.) We can simulate it by nondeterministically guessing the string <span class="math-container">$a=(a_0,\dots,a_{c\log n})$</span> of answers to witness queries made during the computation, and then running the <span class="math-container">$\dlt$</span> verifier.</p>
<p>The catch is we also need to make sure that <span class="math-container">$a$</span> is <em>internally consistent</em>: if the machine happens to ask for the same position twice, it receives the same answer each time. That is, if <span class="math-container">$q_i\in\{0,1\}^{O(\log n)}$</span> denotes the content of the query tape during the <span class="math-container">$i$</span>th witness query, we have
<span class="math-container">$$\forall i,j\le c\log n\:(q_i=q_j\implies a_i=a_j).\tag{$*$}$$</span>
We can test this deterministically by trying all <span class="math-container">$O((\log n)^2)$</span> choices for <span class="math-container">$i,j$</span> and running the <span class="math-container">$O(\log n)$</span> simulation to determine <span class="math-container">$q_i,q_j,a_i,a_j$</span>, in total time <span class="math-container">$O((\log n)^3)$</span>; alternatively, we can select <span class="math-container">$i,j$</span> co-nondeterministically by making <span class="math-container">$2\log\log n+O(1)$</span> universal steps followed by the <span class="math-container">$O(\log n)$</span> deterministic simulation.</p>
<p>We can implement the test more efficiently by universally selecting only <span class="math-container">$i$</span>, and then testing <span class="math-container">$(*)$</span> for all <span class="math-container">$j$</span> in a single <span class="math-container">$O(\log n)$</span>-time pass as follows. We put a copy of <span class="math-container">$q_i$</span> 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 <span class="math-container">$q_i$</span>. Using this information, we can maintain on another work tape a unary counter showing the Hamming distance between <span class="math-container">$q_i$</span> and the current content of the witness query tape. Thus, we know when the machine makes a witness query with <span class="math-container">$q_j=q_i$</span>, and we can check if <span class="math-container">$a_i=a_j$</span>.</p>
<p>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 <span class="math-container">$(*)$</span> does not make any new queries to the original input). Using the standard translation of alternating logarithmic time to bounded-depth circuits (cf. <a href="https://cstheory.stackexchange.com/a/36910">here</a>), this gives:</p>
<blockquote>
<p><strong>Corollary:</strong> Every <span class="math-container">$\exists\dlt$</span> language is recognizable by a <span class="math-container">$\dlt$</span>-uniform family of polynomial-size DNF circuits such that all the conjunctions have fan-in <span class="math-container">$O(\log n)$</span>.</p>
</blockquote>
<p>Some further ideas I tried that did not fare any better:</p>
<ul>
<li><p>Consider the relevant part of the existential witness as a partial Boolean function <span class="math-container">$\{0,1\}^{O(\log n)}\to\{0,1\}$</span> with domain of size <span class="math-container">$O(\log n)$</span>, rather than just a sequence of the query answer bits. This obviates the necessity of checking <span class="math-container">$(*)$</span>. The simplest way to represent the partial witness is a list of all queries along with answers; this takes <span class="math-container">$O((\log n)^2)$</span> bits, and <span class="math-container">$O((\log n)^2)$</span> time to look up each answer, hence the total time is <span class="math-container">$O((\log n)^3)$</span>.</p>
<p>The most efficient representation of the partial witness I know of is by an ordered decision tree with <span class="math-container">$O(\log n)$</span> nodes (see <a href="https://cstheory.stackexchange.com/a/48136">here</a>); this needs <span class="math-container">$O(\log n\log\log n)$</span> bits to write down, and <span class="math-container">$O(\log n\log\log n)$</span> time to evaluate each query, leading to a nondeterministic algorithm that makes <span class="math-container">$O(\log n\log \log n)$</span> nondeterministic guesses followed by <span class="math-container">$O((\log n)^2\log\log n)$</span> deterministic steps.</p>
</li>
<li><p>Instead of checking all <span class="math-container">$O((\log n)^2)$</span> pairs <span class="math-container">$i,j$</span> in <span class="math-container">$(*)$</span>, sort them first. That is, we consider the witness queries as (key,value) pairs <span class="math-container">$(i,q_i)$</span>; we take the array <span class="math-container">$[0,\dots,c\log n]$</span> of the keys, and sort them according to the values. The array takes <span class="math-container">$O(\log n\log\log n)$</span> bits; the sorting can be done with <span class="math-container">$O(\log n\log\log n)$</span> comparisons, but each of those takes time <span class="math-container">$O(\log n)$</span>, hence the overall time is <span class="math-container">$O((\log n)^2\log\log n)$</span>. Alternatively, we may <em>guess</em> 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.</p>
</li>
</ul>

CC BY-SA 4.0
2021-06-26T10:19:03.540Z
Just to call out the core difficulty if someone else like me didn't get it on first read: the existential one can read from a poly size witness log n bits it chooses, the nondeterministic one can only guess and store log n bits, not the entire witness, so it has to somehow use that to answer log n queries in a consistent manner. If it could guess and store log n log log n bits (location, value) it could be done, but we can only log n bits, so need some ingenuous way of using only that many bits.
Kaveh
CC BY-SA 4.0
2021-06-26T10:22:58.327Z
My sense is that it is probably not true, so might worth spending sometime to find a counter example. Are the existential ones with restricted witness sizes of log n and log n log log n equivalent?
Kaveh
CC BY-SA 4.0
2021-01-25T20:39:53.227Z
OMG, Emil Jeřábek asked a question!
domotorp
CC BY-SA 4.0
2021-01-26T07:19:08.283Z
@domotorp I knew it was rare when I liked your comment, but then I checked and it is *literally* the first!
Joshua Grochow
CC BY-SA 4.0
2021-01-26T13:53:54.537Z
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.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-01-26T16:38:59.543Z
@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.
Emil Jeřábek
CC BY-SA 4.0
2021-01-26T16:52:18.837Z
@domotorp I took the liberty to steal your notation for the answers, as it is indeed more suggestive.
Emil Jeřábek
CC BY-SA 4.0
2021-01-26T19:05:25.683Z
Sure. Also, I've undeleted my answer, because it looks like others have similar ideas.
domotorp
CC BY-SA 4.0
2021-01-26T22:43:04.773Z
I don't believe we are thinking of the same thing. What I suggest is to make use of a (large) array, initialized in time O(1), to store the witness. So when the algorithm makes a query at address q of the binary witness, we perform a read from index q of the array to see if a guess was already recorded. If not a nondeterministic guess is made and stored for possible later use.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-01-26T23:09:51.780Z
@Kristoffer You mean to use an $n^{O(1)}$-size array with $O(\log n)$ bits filled in? Could you be more specific how to implement such a structure on a Turing machine? Note that the only thing you have random access to is the input (because it would be too large to be read otherwise). Work tapes work as usual on a TM: you access them using a head that can only move one step a time. (In particular, they are effectively limited to length $O(\log n)$ if the machine runs in $O(\log n)$ time.)
Emil Jeřábek
CC BY-SA 4.0
2021-01-26T23:16:49.537Z
I see, yes I was imagining having also random access work tapes available.
Kristoffer Arnsfelt Hansen
<complexity-classes><nondeterminism>
NLOGTIME versus $\exists$DLOGTIME
Emil Jeřábek
# NLOGTIME versus $\exists$DLOGTIME

(Asked by: username_0 on 2021-01-25)

$\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](https://cstheory.stackexchange.com/a/36910)), 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](https://cstheory.stackexchange.com/a/48136)); 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.

**Tags:** complexity-classes, nondeterminism
> **Comments:**
> **username_2**: OMG, Emil Jeřábek asked a question!  
> **username_3**: @domotorp I knew it was rare when I liked your comment, but then I checked and it is *literally* the first!  
> **username_4**: 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.  
> **username_0**: @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.  
> **username_0**: @domotorp I took the liberty to steal your notation for the answers, as it is indeed more suggestive.  
> **username_2**: Sure. Also, I've undeleted my answer, because it looks like others have similar ideas.  
> **username_4**: I don't believe we are thinking of the same thing. What I suggest is to make use of a (large) array, initialized in time O(1), to store the witness. So when the algorithm makes a query at address q of the binary witness, we perform a read from index q of the array to see if a guess was already recorded. If not a nondeterministic guess is made and stored for possible later use.  
> **username_0**: @Kristoffer You mean to use an $n^{O(1)}$-size array with $O(\log n)$ bits filled in? Could you be more specific how to implement such a structure on a Turing machine? Note that the only thing you have random access to is the input (because it would be too large to be read otherwise). Work tapes work as usual on a TM: you access them using a head that can only move one step a time. (In particular, they are effectively limited to length $O(\log n)$ if the machine runs in $O(\log n)$ time.)  
> **username_4**: I see, yes I was imagining having also random access work tapes available.  
> **username_1**: Just to call out the core difficulty if someone else like me didn't get it on first read: the existential one can read from a poly size witness log n bits it chooses, the nondeterministic one can only guess and store log n bits, not the entire witness, so it has to somehow use that to answer log n queries in a consistent manner. If it could guess and store log n log log n bits (location, value) it could be done, but we can only log n bits, so need some ingenuous way of using only that many bits.  
> **username_1**: My sense is that it is probably not true, so might worth spending sometime to find a counter example. Are the existential ones with restricted witness sizes of log n and log n log log n equivalent?  

---

## 2 answers

### Answer by username_5 on 2021-06-30. Score: 5 | Accepted answer

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 *i*th 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.

> **Comments:**
> **username_0**: I was confused at first by the sums, but now I get it. The idea is to use a hashing function to compress the $O(\log n)$ witness queries of length $O(\log n)$ to length $O(\log\log n)$ each. The crucial thing is that this can be done in such a way that a single-bit update of the query tape can be simulated in time $O(\log\log n)$ rather than $O(\log n)$. This can be accomplished e.g. by taking the query value modulo a fixed $O(\log\log n)$-bit number $p$ for the hash function: updating the hash then amounts to addition or subtraction mod $p$. The consistency of the list of query hashes and ...  
> **username_0**: ... the corresponding replies can be checked by sorting the list. By my reckoning, all this can be implemented by nondeterministically guessing $O(\log n)$ bits, followed by $O(\log n(\log\log n)^2)$-time deterministic computation. Well done! I am still interested if the time can be brought all the way down to $O(\log n)$.  

---

### Answer by username_2 on 2021-01-25. Score: 0

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

> **Comments:**
> **username_0**: 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.)  

---

