2
$\begingroup$

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?

$\endgroup$
2
  • 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$ – David Richerby Apr 23 '17 at 11:33
  • 1
    $\begingroup$ What does "divide" mean here, precisely? That is essential. $\endgroup$ – Raphael Apr 23 '17 at 15:39
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy