Let $A$ be a problem. I would like to solve $A$ in $NL$. So, I am trying to construct Turing machine working in $NL$:

Let $w$ be a input of length $n$. Firstly, we run machine $M_1$ that working in $LOGSPACE$. It produces a output $o$ of length $P(n)$ where $P$ is a polynomial. Secondly, a machine $M_2$ working in $NL$ reads the output $o$ written by $M_1$.

Does t work in $NL$? Why?

P.S. If machine $M_2$ worked in $L$ it would be obvious that problem is solvable in $L$. But, I am not sure if that algorithm solves $A$ in $NL$.


$M_2$, while running on $w$, calls $M_1(w)$ as a subroutine. So if $M_1(w)$'s output is stored on $M_2$'s working tape then it requires polynomial space, not logarithmic space. So, $M_2$ does not work in logarithmic space no matter it is deterministic or nondeterministic.

Of course you could design your machine $M_2$ so that $M_1(w,i)$ would return $i$th bit on demand (on each call). In this case it would work in logarithmic space. But it depends on the problem you solve.


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.