Tag Info

Hot answers tagged space-complexity

2

You can write $x$ and $y$ in binary as \begin{align} x&=x_{M-1} \ldots x_0 \\ y&=y_{M-1} \ldots y_0 \end{align} (This is exactly the contents of your arrays.) Since $x \neq y$, there must be a first bit (from the left) at which they differ. Say that this bit is $x_i \neq y_i$. Since $y > x$, we know that $y_i = 1$ and $x_i = 0$. Thus \begin{align} ...

2

We usually assume that a reasonable proportion of entries in a hash table are used, or we would be wasting memory. If we know that a hash table is at least 20% full then we can just visit random locations until we find a used one , five or so in this case (starting with a random entry and checking consecutive entries wouldn’t work with badly distributed hash ...

1

There is an interesting language that is $\Theta({loglog(n)})$, I found it in the free google book preview of the book "Turing Machines with Sublogarithmic Space", Here is the language: $C = \{a^n|F(n)\text{ is a power of 2}\}$ $F(n)=\min\{i|i\text{ does not divide n}\}$ It is $\Theta(\log\log(n))$ because of the following construction of an accepting ...

1

$C_2 \subseteq NL$: Let $L \in C_2$. Let the log-space verifier for $L$ be $T$. We can construct a log-space NTM $T'$ which on any input simulates $T$ on the same input. Whenever $T$ tries to read the witness-tape, $T'$ just non-deterministically guesses an alphabet. This will have the same effect as having a read-once witness tape.

1

Let $N$ be the total number of configurations of the machine other than the witness tape, namely state, location of the input tape head, contents of the work tape, and location of the work tape head. Note that $N$ is polynomial in $n$. We can assume without of generality that at each step, the machine reads a bit from the witness tape, and it affects its ...

1

There is no need to store the new graph on the tape. We just need to be able to output it in logspace. This is straightforward, for any reasonable encoding of graphs.

1

To answer your first question, this is tremendously unimportant. You typically don't encounter "funny" functions in actual complexity classes you may encounter in practice. Also, the answer to your question might depend on the exact definitions, which is a sign that you shouldn't be considering these complexity classes in the first place. That said, probably ...

1

You can do this using $O(1)$ space, using two pointers. Initially, the first pointer is at the left end of the input, and the second pointer is at its right end. Each round, advance both pointers toward the middle, until they meet. This requires no additional space at all! (The latter, assuming we can enlarge the tape alphabet. Otherwise we can still make ...

1

You can do this with constant amount of memory (according to your definition of space complexity). Assume $n \ge 2$ (the complementary case is trivial). Mark the work tape on the starting position of the input, then move right until you reach the end of the input and mark the last position of the input on the work tape. Repeat the following: Go back to ...

1

Hint: let $n={k \choose k/2}$. Consider the state of the algorithm after reading $n/2$ of the sequences. How many possible states are there, that it could be in at that point?

Only top voted, non community-wiki answers of a minimum length are eligible