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.

  • 3
    $\begingroup$ 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. $\endgroup$ – chazisop Dec 24 '10 at 8:54
  • 1
    $\begingroup$ @chazisop: this is one of the surveys I have also found, everything seems to be at least ten years old on the topic. $\endgroup$ – domotorp Dec 24 '10 at 10:12
  • 1
    $\begingroup$ I think @Kaveh is referred to this post. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 24 '10 at 11:10
  • 2
    $\begingroup$ Your memory is indeed vague, the theorem is that any TM using o(log log n) space must be regular. $\endgroup$ – domotorp Dec 4 '12 at 0:31
  • 4
    $\begingroup$ @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) (dx.doi.org/10.1016/0304-3975(85)90165-3) building off of Hennie (1965) (dx.doi.org/10.1016/S0019-9958(65)90399-2), who showed that linear-time one-tape TMs decide only regular languages and introduced crossing sequences. $\endgroup$ – 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.

  • 5
    $\begingroup$ 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. $\endgroup$ – domotorp Dec 25 '10 at 9:06
  • 2
    $\begingroup$ @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. $\endgroup$ – Hsien-Chih Chang 張顯之 Dec 25 '10 at 12:58

If LOGLOG = NLOGLOG then LOG = NLOG. See more in:


and therefore, your question is still an unsolved problem.

  • 2
    $\begingroup$ This is one of the papers I was referring to when I wrote "I could only find some older surveys and a theorem that if they equal then L=NL". $\endgroup$ – domotorp Mar 8 '20 at 21:22

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.