34

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.

domotorp
  • 13,931
  • 37
  • 93
  • 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. – chazisop Dec 24 '10 at 08:54
  • 1
    @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
  • 1
    I think @Kaveh is referred to this post. – Hsien-Chih Chang 張顯之 Dec 24 '10 at 11:10
  • Thanks! However, this has little to do with my question, the OR obviously won't work here. – domotorp Dec 24 '10 at 11:53
  • 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 Dec 03 '12 at 18:07
  • 2
    Your memory is indeed vague, the theorem is that any TM using o(log log n) space must be regular. – domotorp Dec 04 '12 at 00:31
  • 4
    @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 Dec 04 '12 at 04:31
  • 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], so I'm pretty sure $L'$ is in NLOGLOG. Can anyone show $L'$ is (or is not) in LOGLOG? – Neal Young Dec 04 '12 at 05:56
  • 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 Dec 04 '12 at 08:44
  • 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#". – Neal Young Dec 04 '12 at 17:05
  • Yes, that's what I had in mind. – domotorp Dec 05 '12 at 12:15
  • 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, 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 Dec 13 '12 at 04:26

2 Answers2

18

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.

Hsien-Chih Chang 張顯之
  • 7,638
  • 4
  • 44
  • 83
  • 5
    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 09:06
  • 2
    @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
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.

Frank Vega
  • 119
  • 7
  • 2
    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 Mar 08 '20 at 21:22