6
$\begingroup$

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!!!

$\endgroup$
6
$\begingroup$

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$.

| cite | 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.