

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

Define LOGLOG as the class of languages which can be computed in space O(loglog n) by a deterministic Turing machine (with two-way access to the input). Similarly define NLOGLOG as the class of languages which can be computed in space O(log log n) by a non-deterministic Turing machine (with two-way access to the input). Is it really not known that these classes differ?

I could only find some older surveys and a theorem that if they equal then L=NL (which is not just a trivial padding argument!), but somehow I feel that separating these classes cannot be that hard. Of course I might be completely wrong, but if every second bit of the input is the numbers from 1 to n in increasing order in binary, separated by some symbols, then the machines can already learn loglog n and with every other second bit we can input a problem that can fool a deterministic machine but not a non-deterministic one. I don't see yet exactly how this could be done but feels like a possible approach, as with this trick we can basically input a depth log n binary tree along with its structure instead of the usual linear tape.

share|cite|improve this question
From a quick search, I found the paper "Computing with Sublogarithmic Space" by Maciej Liskiewicz and Rudiger Reischuk. Also, it seems that in sublogarithmic space, class relations depend heavily on the model used. – chazisop Dec 24 '10 at 8:54
@chazisop: this is one of the surveys I have also found, everything seems to be at least ten years old on the topic. – domotorp Dec 24 '10 at 10:12
I think @Kaveh is referred to this post. – Hsien-Chih Chang 張顯之 Dec 24 '10 at 11:10
Your memory is indeed vague, the theorem is that any TM using o(log log n) space must be regular. – domotorp Dec 4 '12 at 0:31
@domotorp: both statements are theorems, but for $o(n \log n)$ you need single-tape. (Of course, for $SPACE(o(\log \log n))$ you can also assume one-tape, since the multi-tape to one-tape translation doesn't increase space.) The reference Neal Young was looking for is: Kobayashi (1985) ( building off of Hennie (1965) (, who showed that linear-time one-tape TMs decide only regular languages and introduced crossing sequences. – Joshua Grochow Dec 4 '12 at 4:31

The entry in the complexity zoo is surprisingly detailed; it claims that NLOGLOG = co-NLOGLOG in the paper

Nondeterministic computations in sublogarithmic space and space constructibility, Viliam Geffert, SIAM Journal on Computing, 1991.

But after a brief reading, I do not see any claim about the fact that NLOGLOG is closed under complement; maybe a deeper look is needed. And the main result they have is that there are no nondeterministic fully space-constructible unbounded monotone increasing $s(n)$ functions for $s(n) = o(\log n)$. It is known that if such functions exists, then

$\mathsf{SPACE}[s(n)] \neq \mathsf{NSPACE}[s(n)]$.

And in the conclusion the author claimed that " ...this main separation problem remains open. "

As @chazisop said, the relations of these low-level complexity classes are depended on the models, and it is stated in the entry of the zoo that

"There are several possible definitions of this class; the most common is the class of languages which can be computed in space O(log log n) by a deterministic Turing machine with two-way access to the input. "

Which is coincident to your definition and also the paper's.

share|cite|improve this answer
I think it only claims NLOGLOG=co-NLOGLOG. I also could not find this statement in the abstract of the paper, though I could not open the full paper. – domotorp Dec 25 '10 at 9:06
@domotorp: You are right. I feel really embarrassing to my wrong answer... I'm too tired even misread the sentences, Maybe I should take a break for Christmas. – Hsien-Chih Chang 張顯之 Dec 25 '10 at 12:58
Thank you for the link to the paper. Merry Christmas! – domotorp Dec 25 '10 at 19:22

Your Answer


