<p>Define the language <span class="math-container">$BACKPOINTER$</span> to have words of length <span class="math-container">$n+t\log n$</span>, divided to <span class="math-container">$1+t$</span> parts, one of length <span class="math-container">$n$</span> and the rest of length <span class="math-container">$\log n$</span>, by commas such that <span class="math-container">$BACKPOINTER=\{(x,p_1,\ldots,p_t)\mid x_{p_i}=1 \forall i\}$</span>.
It should follow from some standard one-way communication complexity bound that <span class="math-container">$BACKPOINTER$</span> needs at least <span class="math-container">$t$</span> bits of memory stored after <span class="math-container">$x$</span> is read. So for any <span class="math-container">$t\gg \log n$</span>, <span class="math-container">$BACKPOINTER\in L\setminus 1NL$</span>.</p>

<p>ps. Note that <span class="math-container">$BACKPOINTER\in 1co\text{-}NL$</span>.</p>

CC BY-SA 4.0
2020-03-09T10:17:13.360Z
2020-03-09T10:17:13.360Z
domotorp
<p>A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most <span class="math-container">$O(\log n)$</span> space in its read-write work tapes. The classes <span class="math-container">$L$</span> and <span class="math-container">$NL$</span> contain those languages which are decided by deterministic or nondeterministic log-space Turing machines, respectively. The two-way Turing machines may move their head on the input tape into two-way (left and right directions) while the one-way Turing machines are not allowed to move the input head on the input tape to the left. </p>

<p>Hartmanis and Mahaney have investigated the classes <span class="math-container">$1L$</span> and <span class="math-container">$1NL$</span> of languages recognizable by deterministic one-way log-space Turing machine and nondeterministic one-way log-space Turing machine, respectively. They have shown that <span class="math-container">$1NL \subseteq L$</span> if and only if <span class="math-container">$L=NL$</span>.</p>

<p>See the paper here(it is free to download):</p>

<p><a href="https://ecommons.cornell.edu/handle/1813/6253" rel="noreferrer">https://ecommons.cornell.edu/handle/1813/6253</a></p>

<p>I wonder this question:</p>

<p>Is <span class="math-container">$L \subset 1NL$</span> when <span class="math-container">$L \neq NL$</span>?</p>

<p>Moreover, I wonder this another question:</p>

<p>Is there any reference that shows whether at least one of the options <span class="math-container">$L \subset 1NL$</span> or <span class="math-container">$1NL \subset L$</span> or <span class="math-container">$L = 1NL$</span> should be true?</p>

<p>Thanks in advance!!! </p>

CC BY-SA 4.0
2020-03-12T22:41:37.497Z
Cross-posted: https://cstheory.stackexchange.com/q/46449/5038, https://cs.stackexchange.com/q/121583/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
<cc.complexity-theory><complexity-classes><turing-machines><nondeterminism><space-complexity>
Is $L \subset 1NL$ when $L \neq NL$?
Frank Vega
# Is $L \subset 1NL$ when $L \neq NL$?

(Asked by: username_0 on 2020-03-08)

A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which are decided by deterministic or nondeterministic log-space Turing machines, respectively. The two-way Turing machines may move their head on the input tape into two-way (left and right directions) while the one-way Turing machines are not allowed to move the input head on the input tape to the left.

Hartmanis and Mahaney have investigated the classes $1L$ and $1NL$ of languages recognizable by deterministic one-way log-space Turing machine and nondeterministic one-way log-space Turing machine, respectively. They have shown that $1NL \subseteq L$ if and only if $L=NL$.

See the paper here(it is free to download):

<https://ecommons.cornell.edu/handle/1813/6253>

I wonder this question:

Is $L \subset 1NL$ when $L \neq NL$?

Moreover, I wonder this another question:

Is there any reference that shows whether at least one of the options $L \subset 1NL$ or $1NL \subset L$ or $L = 1NL$ should be true?

Thanks in advance!!!

**Tags:** cc.complexity-theory, complexity-classes, turing-machines, nondeterminism, space-complexity

> **Comments:**
> **username_1**: Cross-posted: https://cstheory.stackexchange.com/q/46449/5038, https://cs.stackexchange.com/q/121583/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  

---

## 1 answers

### Answer by username_2 on 2020-03-09. Score: 6 | Accepted answer

Define the language $BACKPOINTER$ to have words of length $n+t\log n$, divided to $1+t$ parts, one of length $n$ and the rest of length $\log n$, by commas such that $BACKPOINTER=\{(x,p\_1,\ldots,p\_t)\mid x\_{p\_i}=1 \forall i\}$.
It should follow from some standard one-way communication complexity bound that $BACKPOINTER$ needs at least $t$ bits of memory stored after $x$ is read. So for any $t\gg \log n$, $BACKPOINTER\in L\setminus 1NL$.

ps. Note that $BACKPOINTER\in 1co\text{-}NL$.


---

