By the definition of L=DLOGSPACE or of NL=NLOGSPACE (or any sublinear space class) there is an extra tape (for the Turing machine): the input tape, which is only for reading - but for arbitrary reading. The machine can read the first 10 cells and then maybe go back to read the 1st und 2nd cell.

My question is: If we restrict the way of reading that every cell is read only one time (in one direction: the 1st, 2nd, 3rd,... to the last cell of the input - and then nothing can be read of the input tape!), will we get same classes L and NL or will we lose some languages?


1 Answer 1


For a complexity class $\mathcal{C}$, we can define read-$k$-times $\mathcal{C}$ to be the set of problems $S \in \mathcal{C}$ for which there exists a $k$ such that an accepting computation for $S$ on input $w$ reads each bit at most $k$.

A consequence of a result from On lower bounds for read-$k$-times branching programs (1991) by Borodin, Razborov and Smolensky gives a separation between deterministic log space with unbounded reads and non-deterministic log space with bounded reads:

Proposition: There is a problem $S$ for which $S \in L$ but $S \not\in \text{read-}k\text{-times } NL$.

This means, to answer your question, we lose some languages since $L \not\subseteq \text{read-}k\text{-times }NL$ but $L \subseteq NL$.

My source of this proposition is from DynFO: A Parallel, Dynamic Complexity Class due to Patnaik & Immerman, who cite the BRS paper.

  • 1
    $\begingroup$ Very interesting! Do you know a concrete example for such a Set $S$? $\endgroup$
    – rl1
    Jul 17, 2017 at 7:03

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.