<p>The <a href="http://complexity-zoo.net/zoo/wiki/Complexity_Zoo%3aL#loglog">entry in the complexity zoo</a> is surprisingly detailed; it claims that 
<strong>NLOGLOG</strong> = <strong>co-NLOGLOG</strong> in the paper </p>

<blockquote>
  <p><a href="http://dl.acm.org/citation.cfm?id=114454">Nondeterministic computations in sublogarithmic space and space constructibility</a>, Viliam Geffert, SIAM Journal on Computing, 1991.</p>
</blockquote>

<p>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 </p>

<p>$\mathsf{SPACE}[s(n)] \neq \mathsf{NSPACE}[s(n)]$. </p>

<p>And in the conclusion the author claimed that " ...this main separation problem remains <em>open</em>. "</p>

<p>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</p>

<blockquote>
  <p>"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. "</p>
</blockquote>

<p>Which is coincident to your definition and also the paper's.</p>

CC BY-SA 2.5
2010-12-25T09:06:21.723Z
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
CC BY-SA 2.5
2010-12-25T12:58:48.833Z
@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 張顯之
CC BY-SA 3.0
2010-12-25T07:15:33.187Z
2012-12-04T03:29:01.953Z
2012-12-04T03:29:01.953Z
Hsien-Chih Chang 張顯之
<p>If LOGLOG = NLOGLOG then LOG = NLOG. See more in:</p>

<p><a href="https://www.sciencedirect.com/science/article/pii/0304397590900086" rel="nofollow noreferrer">https://www.sciencedirect.com/science/article/pii/0304397590900086</a></p>

<p>and therefore, your question is still an unsolved problem.</p>

CC BY-SA 4.0
2020-03-08T21:22:55.610Z
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".
domotorp
CC BY-SA 4.0
2020-03-08T20:33:31.640Z
2020-03-08T20:33:31.640Z
Frank Vega
<p>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?</p>

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

CC BY-SA 3.0
2012-12-03T18:07:19.547Z
FWIW, I have a vague memory that any language accepted by a single-tape TM running in time $o(n \log n)$ must be regular.  I think the proof is by a crossing-sequence argument.  I don't know the reference.  (I realize this is not directly relevant to your problem, since LOGLOG space does not imply $o(n\log n)$ time, but I thought the crossing-sequence argument for that problem might conceivably be interesting for LOGLOG space as well.)
Neal Young
CC BY-SA 3.0
2012-12-04T00:31:16.440Z
Your memory is indeed vague, the theorem is that any TM using o(log log n) space must be regular.
domotorp
CC BY-SA 3.0
2012-12-04T04:31:21.983Z
@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) (http://dx.doi.org/10.1016/0304-3975(85)90165-3) building off of Hennie (1965) (http://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.
Joshua Grochow
CC BY-SA 3.0
2012-12-04T05:56:30.283Z
Here's a strawman candidate for separating the two:
the language
$L' = \{0,1,\#\}^*\, L\, \{0,1,\#\}^*$
where $L$ is 
$\{b_k(0)\#b_k(1)\#\cdots\#b_k(2^k-1)\# ~~|~ k=1,2,3,\ldots\}$,
where $b_k(i)$ is the $k$-bit binary representation of $i$.
$L$ is in LOGLOG
[[reference](http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l4.ps)],
so I'm pretty sure $L'$ is in NLOGLOG.
Can anyone show $L'$ is (or is not) in LOGLOG?
Neal Young
CC BY-SA 3.0
2012-12-04T08:44:18.367Z
Wow, I feel ashamed that I did not know this theorem, thanks for the links! Also, I think L' is in LOGLOG as we can just try running the algorithm for L at every sequence of all 0's and if we fail, we can go to the next sequence of all 0's.
domotorp
CC BY-SA 3.0
2012-12-04T17:05:34.360Z
But with just LOGLOG space, it is not clear to me how to keep track of the current starting point.  Perhaps you can modify the algorithm for L so that if, during its computation, it finds "#00..0#" (invalidating the current try), then it resets and starts over at that new #00..0#".
Neal Young
CC BY-SA 3.0
2012-12-05T12:15:58.447Z
Yes, that's what I had in mind.
domotorp
CC BY-SA 3.0
2012-12-13T04:26:05.000Z
The problem is intriguing.  Here is a problem that seems related: can any $n$-state two-way non-deterministic finite automata be simulated by a poly$(n)$-state two-way deterministic finite automata?  From [these talk slides](http://pighizzini.di.unimi.it/talks/2010/Porto.pdf), it appears that the answer is unknown.   Curiously, this question restricted to *unary* languages (roughly, with some assumptions) is apparently equivalent to whether L = NL.
Neal Young
CC BY-SA 2.5
2010-12-24T08:54:04.853Z
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
CC BY-SA 2.5
2010-12-24T10:12:46.993Z
@chazisop: this is one of the surveys I have also found, everything seems to be at least ten years old on the topic.
domotorp
CC BY-SA 2.5
2010-12-24T11:10:21.507Z
I think @Kaveh is referred to [this post](http://cstheory.stackexchange.com/q/3836/1800).
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-24T11:53:31.860Z
Thanks! However, this has little to do with my question, the OR obviously won't work here.
domotorp
<cc.complexity-theory><reference-request><space-bounded>
Does LOGLOG = NLOGLOG?
domotorp
# Does LOGLOG = NLOGLOG?

(Asked by: username_0 on 2010-12-24)

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.

**Tags:** cc.complexity-theory, reference-request, space-bounded

> **Comments:**
> **username_3**: 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.  
> **username_0**: @username_3: this is one of the surveys I have also found, everything seems to be at least ten years old on the topic.  
> **username_4**: I think @Kaveh is referred to [this post](http://cstheory.stackexchange.com/q/3836/1800).  
> **username_0**: Thanks! However, this has little to do with my question, the OR obviously won't work here.  
> **username_1**: FWIW, I have a vague memory that any language accepted by a single-tape TM running in time $o(n \log n)$ must be regular.  I think the proof is by a crossing-sequence argument.  I don't know the reference.  (I realize this is not directly relevant to your problem, since LOGLOG space does not imply $o(n\log n)$ time, but I thought the crossing-sequence argument for that problem might conceivably be interesting for LOGLOG space as well.)  
> **username_0**: Your memory is indeed vague, the theorem is that any TM using o(log log n) space must be regular.  
> **username_2**: @username_0: 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 username_1 was looking for is: Kobayashi (1985) (http://dx.doi.org/10.1016/0304-3975(85)90165-3) building off of Hennie (1965) (http://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.  
> **username_1**: Here's a strawman candidate for separating the two: the language $L' = \{0,1,\#\}^*\, L\, \{0,1,\#\}^*$ where $L$ is  $\{b_k(0)\#b_k(1)\#\cdots\#b_k(2^k-1)\# ~~|~ k=1,2,3,\ldots\}$, where $b_k(i)$ is the $k$-bit binary representation of $i$. $L$ is in LOGLOG [[reference](http://www.wisdom.weizmann.ac.il/~oded/PS/CC/l4.ps)], so I'm pretty sure $L'$ is in NLOGLOG. Can anyone show $L'$ is (or is not) in LOGLOG?  
> **username_0**: Wow, I feel ashamed that I did not know this theorem, thanks for the links! Also, I think L' is in LOGLOG as we can just try running the algorithm for L at every sequence of all 0's and if we fail, we can go to the next sequence of all 0's.  
> **username_1**: But with just LOGLOG space, it is not clear to me how to keep track of the current starting point.  Perhaps you can modify the algorithm for L so that if, during its computation, it finds "#00..0#" (invalidating the current try), then it resets and starts over at that new #00..0#".  
> **username_0**: Yes, that's what I had in mind.  
> **username_1**: The problem is intriguing.  Here is a problem that seems related: can any $n$-state two-way non-deterministic finite automata be simulated by a poly$(n)$-state two-way deterministic finite automata?  From [these talk slides](http://pighizzini.di.unimi.it/talks/2010/Porto.pdf), it appears that the answer is unknown.   Curiously, this question restricted to *unary* languages (roughly, with some assumptions) is apparently equivalent to whether L = NL.  

---

## 2 answers

### Answer by username_4 on 2010-12-25. Score: 18

The [entry in the complexity zoo](http://complexity-zoo.net/zoo/wiki/Complexity_Zoo%3aL#loglog) is surprisingly detailed; it claims that
**NLOGLOG** = **co-NLOGLOG** in the paper

> [Nondeterministic computations in sublogarithmic space and space constructibility](http://dl.acm.org/citation.cfm?id=114454), 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 @username_3 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.

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

---

### Answer by username_5 on 2020-03-08. Score: 1

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

<https://www.sciencedirect.com/science/article/pii/0304397590900086>

and therefore, your question is still an unsolved problem.

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

---

