21
$\begingroup$

Consider language $ \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} $.

It is known that $ \mathtt{EQUALITY} $ cannot be recognized by any sublogarithmic-space alternating Turing machine (ATM) (Szepietowski, 1994). (There is an ATM using sublogarithmic space for members but not for all non-members!)

On the other hand, Freivalds (1981) showed that bounded-error constant-space probabilistic Turing machines (PTMs) can recognize $ \mathtt{EQUALITY} $ but only in exponential expected time (Greenberg and Weiss, 1986). Later, it was shown that no bounded-error $ o(\log\log n) $-space PTM can recognize a non-regular language in polynomial expected time (Dwork and Stockmeyer, 1990). My question is

whether poly-time sublogarithmic-space PTMs recognize $ \mathtt{EQUALITY} $ with bounded-error.

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ I do not understand why the question title has been edited to remove the definition of the language from it. Nobody is going to imagine that "do equality check" means "decide the language $\{a^nb^n\mid n\geq 0\}$. $\endgroup$
    – David Richerby
    Sep 27 '13 at 23:38
  • 1
    $\begingroup$ @DavidRicherby: Thanks for your editing suggestion and comment. I just prefer less technical titles. Otherwise, I should add not only the definition of the language but also the terms "recognized", "bounded-error", and "probabilistic Turing machines". $\endgroup$
    – Abuzer Yakaryilmaz
    Sep 28 '13 at 3:08
  • 2
    $\begingroup$ The title should tell people what the question is about. This is a community of TCS researchers and every TCS researcher knows what "recognized", "bounded-error" and "probabilistic Turing machine" means. Likewise, "$\{a^nb^n\mid n\geq 0\}$" is instantly comprehensible to TCS researchers; "do equality check" is not. If the langauge $\{a^nb^n\mid n\geq 0\}$ had a commonly understood name, using that name would be fine but, as far as I'm aware, it doesn't. $\endgroup$
    – David Richerby
    Sep 28 '13 at 10:43
  • 1
    $\begingroup$ Is there a non-regular unary language that can be recognized in $o(\log n)$ space (on a deterministic TM)? If there isn't, the same proof might work here. $\endgroup$
    – domotorp
    Oct 1 '13 at 19:50
  • $\begingroup$ @domotorp: Yes, there are non-regular languages recognized by $ \log\log n $-space deterministic TMs. (See (Szepietowski, 1994) given above.) $\endgroup$
    – Abuzer Yakaryilmaz
    Oct 2 '13 at 5:34
8
$\begingroup$

I have found an answer to my own question. The result was given in Section 5 of Karpinski and Verbeek, 1987.

For any input of length $ n $, a PTM can construct $ \Theta(\log \log n) $ space with high probability (Section 4). (With a very small probability, the machine can also construct logarithmic space, and this might be seen as a "drawback" of the algorithm.) Then, the PTM can decide whether the numbers of $a$'s ($n$) and $b$'s ($m$) are equal with high probability by using $ O(\log \log n) $ space in polynomial time.

The idea is as follows. If $ n \neq m $, then $ \exists k \leq 4 \log(n+m) $ such that $ n \not\equiv m \mod k $ (Alt and Mehlron, 1976). The PTM can pick a random $ k $ by using $ O(\log \log n) $ space. $ O(\log \log n) $ is also sufficient to keep a counter and so trying more than half of all possible $k$'s. The case of $ n \neq m $ can be detected with a probability more than $ 1 \over 2 $.

Improve this answer
$\endgroup$

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.