Understanding the definition of the complexity class $LOGSPACE$.

233 Views Asked by At

In the area of complexity classes, the complexity class $LOGSPACE$ or $L$ is defined as:

A language $A$ is in $LOGSPACE$ iff. there exists a deterministic Turing Machine $M$ so that $A=T(M)$ and $M$ modifies at max logarithmic many memory cells.

What does it mean by modifying "logarithmic" many cells? How is that possible? I am a little confused by the wording.

1

There are 1 best solutions below

0
On BEST ANSWER

First, consider time complexity once again. The basic idea is simple. When considering a Turing machine $T_M$, we simply "count" the steps $T_M$ needs to halt for any given input, whereby we usually consider a "step" being a transition made by $T_M$. We can consider time complexity as a function $t_c:\Sigma^* \to \mathbb{N}$ of some algorithm.

Now, space complexity is different. Let us be very naive for a second, then space complexity would be very simple. We just consider the maximum number of cells that $T_M$ ever reads on any input of size $n$, which trivially yields to $n+1$ ($+1$ since $T_M$ needs to evaluate the blank symbol $\epsilon$).

But the general idea is different. Assume that $T_M$ is a three tape Turing machine, whereby one tape is the input tape, one is the output tape and one is the so called work tape. We then define the maximum number of cells used on the work tape as the space used by some algorithm during computation and call it the space complexity. We usually say that the work tape is the only tape which is writable (modifiable) (which makes it equivalent to what we consider as "memory"). We often call the work tape, the "memory" tape of $T_M$. Hence, for any input $x$ of size $n$ we could use substantially less cells then we do on the input tape, e.g. we could have an algorithm using only $log(n)$ cells on the memory tape. And we call the set of problems solvable by using only $O(log(n))$ space $LOGSPACE$ problems.

To summarize: A language $L$ is in $LOGSPACE$ if it can be decided by a deterministic Turing machine using $O(log(n))$ space on the memory tape.