<p>I have found an answer to my own question. The result was given in Section 5 of <a href="http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/1985-1989/854-CS.pdf">Karpinski and Verbeek, 1987</a>.</p>

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

<p>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 $ (<a href="https://domino.mpi-inf.mpg.de/intranet/ag1/ag1publ.nsf/0/0DC1428DF5BE30AFC12571C3001E4E5D/%24file/ICALP76.PDF">Alt and Mehlron, 1976</a>). 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 $.</p>

CC BY-SA 3.0
2013-11-05T19:01:57.287Z
2013-11-05T19:01:57.287Z
Abuzer Yakaryilmaz
<p>Consider language $ \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} $. </p>

<p>It is known that $ \mathtt{EQUALITY} $ cannot be recognized by any sublogarithmic-space alternating Turing machine (ATM) <a href="http://link.springer.com/book/10.1007/3-540-58355-6/page/1">(Szepietowski, 1994)</a>. (There is an ATM using sublogarithmic space for members but not for all non-members!) </p>

<p>On the other hand,  <a href="http://link.springer.com/chapter/10.1007/3-540-10856-4_72">Freivalds (1981)</a> showed that bounded-error constant-space probabilistic Turing machines (PTMs) can recognize $ \mathtt{EQUALITY} $ but only in exponential expected time (<a href="http://www.sciencedirect.com/science/article/pii/0022000086900450">Greenberg and Weiss, 1986</a>). Later, it was shown that no bounded-error $ o(\log\log n) $-space PTM can recognize a non-regular language in polynomial expected time (<a href="http://epubs.siam.org/doi/abs/10.1137/0219069">Dwork and Stockmeyer, 1990</a>). My question is</p>

<blockquote>
  <p>whether poly-time sublogarithmic-space PTMs recognize $ \mathtt{EQUALITY} $ with bounded-error.</p>
</blockquote>

CC BY-SA 3.0
2013-09-27T23:38:52.080Z
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\}$.
David Richerby
CC BY-SA 3.0
2013-09-28T03:08:04.500Z
@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".
Abuzer Yakaryilmaz
CC BY-SA 3.0
2013-09-28T10:43:45.173Z
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.
David Richerby
CC BY-SA 3.0
2013-10-01T19:50:45.247Z
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.
domotorp
CC BY-SA 3.0
2013-10-02T05:34:31.950Z
@domotorp: Yes, there are non-regular languages recognized by $ \log\log n $-space deterministic TMs. (See (Szepietowski, 1994) given above.)
Abuzer Yakaryilmaz
CC BY-SA 3.0
2013-10-02T06:31:23.257Z
Lemma 4.2.1 on Pages 24 and 25 in (See (Szepietowski, 1994).
Abuzer Yakaryilmaz
<space-bounded><polynomial-time>
Can $\{a^nb^n\}$ be recognized in poly-time probabilistic sublogarithmic-space?
Abuzer Yakaryilmaz
# Can $\{a^nb^n\}$ be recognized in poly-time probabilistic sublogarithmic-space?

(Asked by: username_0 on 2013-09-27)

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)](http://link.springer.com/book/10.1007/3-540-58355-6/page/1). (There is an ATM using sublogarithmic space for members but not for all non-members!)

On the other hand, [Freivalds (1981)](http://link.springer.com/chapter/10.1007/3-540-10856-4_72) showed that bounded-error constant-space probabilistic Turing machines (PTMs) can recognize $ \mathtt{EQUALITY} $ but only in exponential expected time ([Greenberg and Weiss, 1986](http://www.sciencedirect.com/science/article/pii/0022000086900450)). 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](http://epubs.siam.org/doi/abs/10.1137/0219069)). My question is

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

**Tags:** space-bounded, polynomial-time
> **Comments:**
> **username_1**: 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\}$.  
> **username_0**: @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".  
> **username_1**: 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.  
> **username_2**: 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.  
> **username_0**: @domotorp: Yes, there are non-regular languages recognized by $ \log\log n $-space deterministic TMs. (See (Szepietowski, 1994) given above.)  
> **username_0**: Lemma 4.2.1 on Pages 24 and 25 in (See (Szepietowski, 1994).  

---

## 1 answers

### Answer by username_0 on 2013-11-05. Score: 8 | Accepted answer

I have found an answer to my own question. The result was given in Section 5 of [Karpinski and Verbeek, 1987](http://theory.cs.uni-bonn.de/ftp/reports/cs-reports/1985-1989/854-CS.pdf).

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](https://domino.mpi-inf.mpg.de/intranet/ag1/ag1publ.nsf/0/0DC1428DF5BE30AFC12571C3001E4E5D/%24file/ICALP76.PDF)). 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 $.


---

