34
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • 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
    Commented Dec 24, 2010 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
    Commented Dec 24, 2010 at 10:12
  • 1
    $\begingroup$ I think @Kaveh is referred to this post. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Dec 24, 2010 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
    Commented Dec 4, 2012 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
    Commented Dec 4, 2012 at 4:31

2 Answers 2

Reset to default
18
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 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
    Commented Dec 25, 2010 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 張顯之
    Commented Dec 25, 2010 at 12:58
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Mar 8, 2020 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.