The Stack Overflow podcast is back! Listen to an interview with our new CEO.
19

FOR x := 1 TO n DO FOR y := 1 TO n DO FOR z := 1 TO n DO IF E(x,y) && E(y,z) && E(z,x) THEN REJECT ACCEPT Each of the variables x, y and z requires $\Theta(\log \texttt{n})$ bits to store an integer between $1$ and $\texttt{n}$.


15

When dealing with restricted space, we use the following model. The Turing machine has three tapes: a read-only input tape, a read-write work tape, and a write-only output tape. We only measure space consumption on the work tape. For palindromes, with space $O(\log n)$ on the work tape we can implement FOR loops that go over the input, comparing matching ...


15

$\sqrt{n}$ space is somewhat unusual; the most likely reason for such a complexity to emerge is as a result of a so-called meet in the middle scheme. Two notable examples off the top of my head are the classical sieve of Eratosthenes and the baby-step giant-step algorithm for the discrete logarithm over a finite group.


15

You don't need to first write all 3-tuples and then check, for each of them, whether it induces a triangle. You can just enumerate the 3-tuples one at a time and reject as soon as you find one that induces a triangle. If you reach past the last 3-tuple then the graph contains no triangle and you can accept.


13

It is an open problem if you can do selection with $O(n)$ time and $O(1)$ extra memory cells without changing the input (see here). But you can come pretty close to this. Munro and Raman proposed an algorithm for selection that runs in $O(n^{1+\varepsilon})$ time while using only $O(1/\varepsilon)$ extra storage (cells). This algorithm leaves the input ...


13

No, any strongly-polynomial time algorithm can be converted into a polynomial time algorithm on a TM by replacing the arithmetic operations with equivalent algorithms in the TM model. That is the whole point of strongly-polynomial vs weakly-polynomial. When you've analysed algorithms in the past, you've probably assumed that your arithmetic operations (...


12

Denote the arrays by $A,B$, and suppose they are of length $n$. Suppose first that the values in each array are distinct. Here is an algorithm that uses $O(1)$ space: Compute the minimum values of both arrays, and check that they are identical. Compute the second minimum values of both arrays, and check that they are identical. And so on. Computing the ...


10

The expression $f(n)2^{O(f(n))}$ is simply an upper bound for the number of all configurations a $f(n)$-space bounded TM can have. Here is how to count: We have $|\Gamma|^{f(n)}=2^{O(f(n)}$ different ways how to fill the work tape, and the head can be on $f(n)$ different positions. There is also a constant number of states where we can currently be, but this ...


10

This phenomenon is known in computer science as a time-space tradeoff. For example, Ryan Williams proved that if a computer solves SAT on instances of size $n$ in time $T$ and using memory $S$ then $T \cdot S \geq n^{1.8}$. (We don't expect this to be tight.) A classical result states that when recognizing palindromes on a Turing machine, $T \cdot S = \Omega(...


10

Look up Blum's speedup theorem (yes, this article is less than informative; look at a book on complexity theory). It essentially says that there are programs for which there is a program doing the same job that is faster by any specified margin for almost all input data. By Rice's theorem, it is impossible to know if two given programs do the same job. Yes,...


9

This algorithm doesn't run in polynomial time, it runs with polynomial delay. As the paper notes: Observe that the number of minimal, and even minimum solutions, can be exponential in the size of the graph; Fig. 1 gives an example. Therefore, the total running time of any enumeration algorithm cannot be expected to be polynomial in the size of the ...


8

IP = PSPACE is a famous result (and indeed paper) by Adi Shamir in 1992. Furthermore, we clearly have NP $\subseteq$ PSPACE and coNP $\subseteq$ PSPACE, but we don't know how NP relates to coNP. There are several reasons to believe that determining the relationship between NP and coNP is difficult, some of which are discussed in this recent thread.


8

In this paper it is proven that there exists a constant $\alpha$ such that the probability of the space exceeding $\alpha n$, is less than $1/2^{\Omega(\sqrt{n})}$. Thefore, the more elements there are, the less likely it is to exceed this space bound.


8

Disclaimer: The following algorithm does not use the standard model for sublinear space complexity (see WP:DSPACE), because it writes to the input tape. Furthermore the set of (Watson-Crick) palindromes is not in $\mathsf{DSPACE}(\mathcal{O}(1)) = \mathsf{REG}$. Nevertheless, it's an in-place solution for many practical purposes (e.g. if each letter is a ...


8

You have to compute two averages, $2n$ differences, three sums with $n$ summands -- which can be computed in constant time -- each and one division, one multiplication and one square root. All of this can be done in linear time if we assume elementary arithmetic operations run in constant time, therefore total time in $O(n)$ is certainly possible. Note ...


8

Immerman–Szelepcsényi theorem works under logarithmic reductions. Sublogarithmic space classes have different reductions. The TMs working within sublogarithmic space cannot even record the the length of the input. It has been shown that the space hierarchy for any sublogarithmic bound in Ω(log log n)-- o(log n) is infinite. You can find it in following ...


8

Joe's answer is extremely good, and gives you all the important keywords. You should be aware that succinct data structure research is still in an early stage, and many of the results are largely theoretical. Many of the proposed data structures are quite complex to implement, but most of the complexity is due to the fact that you need to maintain ...


8

By the same reasoning that NP is in PSPACE, co-NP is in co-PSPACE. But co-PSPACE = PSPACE (you can just flip the answer), so co-NP is in PSPACE, too.


8

The more well-known version of these questions is the $\mathsf{L} \stackrel?= \mathsf{NL}$ question. If $\mathsf{L} = \mathsf{NL}$ then a (slightly tricky) padding argument shows that $\mathsf{DSPACE}(n) = \mathsf{NSPACE}(n)$, and so $\mathsf{DSPACE}(n) \neq \mathsf{NSPACE}(n)$ implies the well-known conjecture $\mathsf{L} \neq \mathsf{NL}$. The conjecture $...


7

Let me give an explanation which does not differ in content from the accepted answer, but brings the question back to the realm of regular languages. The language you are dealing with can be defined as follows. Let $s \in \Sigma^{\mathbb{N}}$ be a (countably) infinite string of symbols from some finite alphabet $\Sigma$, and let $s[1:i]$ be the prefix of ...


7

This is elaborated nicely in Dexter Kozen's Theory of Computation textbook, in chapter 2. Savitch's Theorem (Theorem 1 in his paper) says: if $S(n) \ge \log n$, then $\text{NSPACE}(S(n)) \subseteq \text{DSPACE}(S(n)^2)$. Space-constructibility often seems to be assumed in a proof, but this requirement can be removed by restarting the search with a fixed ...


7

Hint: Suppose $C_1,\ldots,C_\ell$ are the connected components and $v_i$ is the minimal vertex in $C_i$. Suppose further that $v_1 < v_2 < \cdots < v_\ell$. Show how to certify the fact that this data is correct in NL by keeping at most two of these indices at a time. Here are some more details for a slightly simpler problem: verifying whether an ...


7

Memory complexity is the size of work memory used by an algorithm. In the relevant Turing machine model, there is an read-only input tape, a write-only output tape, and a read-write work tape; you're interested only in the work tape. This makes sense since work memory is the additional memory that the specific algorithm uses. For example, if it is called ...


7

I found the answer below in lecture notes of Muli Safra. Consider the language consisting of the following strings: $$ \begin{align*} & 0 \$ 1 \$ \\ & 00 \$ 01 \$ 10 \$ 11 \$ \\ & 000 \$ 001 \$ 010 \$ 011 \$ 100 \$ 101 \$ 110 \$ 111 \$ \\ &\ldots \end{align*} $$ This language can be recognized in space $O(\log\log n)$. For each $m$ which ...


7

Factoring is not known to be even in $\mathsf{P}$. Primality is not known to be in any class conjectured to be smaller than $\mathsf{P}$ (AFAIK).


7

Solving intersection Non-Emptiness for 2 DFA's: It essentially just becomes a reachability problem for the product DFA. Roughly, we can solve it deterministically in $O(n^2)$ time using $O(n^2)$ space. Or, we can solve it non-deterministically with $O(\log(n))$ space. By Savitch's Theorem, we can also solve it deterministically in $2^{O(\log^2(n))}$ time ...


7

No, it is not necessary to remember all $y$'s tried before. In order to remember that I've tried the numbers $1,2,\ldots,200$, I do not need to remember $3,4,5,6,\ldots,199$. If you try them in order, just remembering the last one is enough.


7

The answer really depends on your computation model. On a (fixed) Turing machine, you can count up to $n$ using no space. A better formulation of the question is like this: Is there a function $f\colon \mathbb{N} \to \{0,1\}^*$ satisfying $|f(n)| = o(\log n)$ and a program $P$ such that $P(f(n))$ uses space $O(f(n))$ and outputs $1^n$? It is a basic ...


7

Space classes always only include working space: the model is that we have a read-only input tape and write-only output tape, plus a read-write work tape (or multiple such tapes) on which we're only allowed to use a bounded amount of space. This definition is necessary for something like LOGSPACE to make any sense: if you counted the output as part of the ...


7

The naive approach would be building histograms of both strings and checking whether they are the same. Since we are not allowed to store such a data structure (whose size would be linear to the size of the alphabet) that could be computed in one pass, we need to count the occurences of each possible symbol after the other: function count(letter, string) ...


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