Let's consider the following situation:

We have a problem $\mathsf{L\text{}}$ . We would like to solve it in $LOGSPACE$. Let assume that our problem $\mathsf{L\text{}}$ can be divided to two parts: $A$ and $B$.

We can solve $A$ using computatation model $M_1$ in $LOGSPACE$.

We can solve $B$ using computation model $M_2$ in $LOGSPACE$, $M_1 \neq M_2$

Does it mean that we can solve $P$ in $LOGSPACE$ ? Why?

  • 2
    $\begingroup$ I'm not sure what you mean by solving a problem using some specific computaion model in LOGSPACE. LOGSPACE, by definition, refers to the amount of space used by a Turing machine. (Also, if you're talking about complexity classes, please don't call a problem "$P$" -- that gets really confusing, really fast. ;-) ) $\endgroup$ Apr 23, 2017 at 11:33
  • 1
    $\begingroup$ What does "divide" mean here, precisely? That is essential. $\endgroup$
    – Raphael
    Apr 23, 2017 at 15:39

1 Answer 1


The composition of two logspace functions is again in logspace. This is a classical result that you can try to prove on your own.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.