patternMinor
The read tape in the definition of L and NL (logarithmic space) (DLOGSPACE, NLOGSPACE) (sublinear space)
Viewed 0 times
definitionthespacereadlogarithmicdlogspacenlogspacetapesublinearand
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#78005, answer score: 3
Revisions (0)
No revisions yet.