# Tag Info

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}$.

17

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.

16

Turing machines operating in logarithmic time cannot even read the entire input. This makes them rather uninteresting. What you have in mind is not Turing machines, but random-access machines, for which logarithmic time does make sense. Indeed, the corresponding complexity class exists: DLOGTIME. It is most often used in the context of DLOGTIME-uniform ...

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

Typically, we consider space complexity in terms of Turing machines with: one read-only input tape one write-only output tape however many read-write working tapes you want. The space usage is the number of cells used on the working tapes, so input and output space typically aren't counted. (See, e.g., Section 2.5 of Papadimitriou.) Obviously, we don't ...

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 ...

11

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,...

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 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 ... 9 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 spaceO(\log\log n)$. For each$m$which ... 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 ... 9 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 ... 9 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. 9 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. 9 You're basically there. If the machine uses at most$s(n)$tape cells for inputs of length$n$, then it can't visit more than$C(n)=|Q||\Sigma|^{s(n)}s(n)$different configurations (possible states times possible tape contents times possible head positions). Since the machine decides a language, it must halt for all inputs, which means that it can'... 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 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

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

The Dyck language on any fixed number of symbols can be recognised by a marking automaton, which is a two-way finite automaton that can mark a fixed number of input tape squares. The automaton simply uses a different mark for each type of parenthesis. Since a marking automaton is easily implemented by a Turing machine with a fixed number of logarithmic-sized ...

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

By definition, PSPACE consists of all languages decided by some Turing machine using polynomial space. So every language in PSPACE can be decided by some Turing machine using space $O(n^\ell)$ for some $\ell$. The space hierarchy theorem ensures moreover that for any $\ell$ there is a language in PSPACE which requires space $\Omega(n^\ell)$. Any PSPACE-hard ...

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) ...

7

Reduction from 3-SAT: a variable in 3-SAT becomes a character in your problem and is paired with its negation. Each clause becomes a word. e.g. 3 SAT: (a,b,-c) && (-b,c) => pairs: (a,-a), (b,-b), (c,-c). words: (a,b,-c), (-b,c) Selecting a character in your problem means setting that literal to true in the 3-SAT instance. The corresponding ...

7

First of all, let me give the correct attribution to this algorithm: Cook and McKenzie, Problems complete for deterministic logarithmic space. The setup of Cook and McKenzie is that you are given an undirected graph in which the edges incident to a vertex $v$ are ordered (cyclically), and given one of them it is possible to find the next one in the order. ...

7

This is an example of a dynamic algorithm. I will adapt the algorithm in the link, as I don't think that it is written in the most helpful way. Initialise sum = 0 and maxLen = 0. Create a hash table having (sum, index) tuples. For i = 0 to n-1, perform the following steps: Set sum = sum + arr[i]. If sum == k, update maxLen = i+1, continue from here to next ...

7

EXPSPACE is not the most inclusive computational complexity class. There's a huge number of complexity classes; see, e.g., the Complexity Zoo for some that have been studied (and in principle there are an unlimited number one could define). The space hierarchy theorem shows that for each $f(n)$, there are languages that can be decided in space $f(n)$ but ...

6

A program running in space $f(n)$ can take up to $2^{O(f(n))}$ time (the constant depends on the alphabet size). Hence, it could potentially make up to $2^{O(f(n))}$ non-deterministic choices. Naively, going over all of them requires that many steps. Savitch's theorem shows how this can be accomplished using only $O(f(n)^2)$ space. The idea is to use a ...

6

In a given tree, all the vertices of this tree correspond to binarySum() calls. The value of parameter n to binarySum() is halved at each recursive call. Also, each recursive call finishes after all its children finish. Thus at each recursive call, number of active calls include all the ancestor calls in call sequence. Thus when any binarySum() call ...

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