26
votes
Accepted
Does space complexity analysis usually include output space?
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 ...
- 82.1k
25
votes
Accepted
Does an algorithm's space complexity include input?
It depends on the chosen convention. I often prefer the convention that considers that the input is not part of the space complexity, for different reasons:
the space complexity of a function answer ...
- 16k
19
votes
How is the problem, {⟨G⟩|G has no triangle} in Logspace?
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 ...
- 82.1k
17
votes
Accepted
How is the problem, {⟨G⟩|G has no triangle} in Logspace?
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 ...
- 29.6k
17
votes
Accepted
why does LSPACE(log space) complexity class exist but not logtime?
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 ...
- 279k
15
votes
Algorithms with O(sqrt(N)) SPACE complexity?
$\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 ...
- 4,272
12
votes
How to check if two strings are permutations of each other using O(1) additional space?
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 ...
- 279k
10
votes
Accepted
Why is PH in PSPACE?
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, ...
- 13.4k
9
votes
Accepted
Proving that $\mathrm{SPACE}(o(\log\log n)) = \mathrm{SPACE}(O(1))$?
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 ...
- 82.1k
9
votes
Accepted
Is every PSPACE-complete problem complete with respect to logspace reductions?
If every PSPACE complete problem is also complete under logspace reduction, then $\mathsf{P\neq PSPACE}$.
To see why, suppose for the purpose of contradiction that the definition of completeness ...
- 13.5k
8
votes
Accepted
Can FPSPACE give exponentially long outputs?
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 ...
- 82.1k
8
votes
A language in NSPACE(O(n)) and very likely not in DSPACE(O(n))
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}(...
- 279k
7
votes
Accepted
How hard are PSPACE-complete problems?
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 ...
- 279k
7
votes
Check for balanced parentheses in an expression in log-space
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 ...
- 3,492
7
votes
Accepted
Is it possible to build a computer that would output $10^{10^{100}}$ symbols and halt, without using ~$10^{100}$ space?
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\...
- 279k
7
votes
Accepted
How to check if two strings are permutations of each other using O(1) additional space?
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 ...
- 608
7
votes
Accepted
Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?
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), (...
- 2,511
7
votes
$UCYCLE$ is in $L$
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 ...
- 279k
7
votes
Accepted
Show that NP is not equal to SPACE(n)
In order to prove that $\mathsf{SPACE}(n) \not\subseteq \mathsf{NP}$, you need to identify a language in $\mathsf{SPACE}(n)$ which is not in $\mathsf{NP}$. Not every language in $\mathsf{SPACE}(n)$ ...
- 279k
7
votes
Accepted
Logic behind O(n) solution for 'Maximum length sub-array having given sum'
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 ...
- 461
7
votes
Accepted
Max number of configurations of a Turing Machine
Yes, that's right. If there are $k$ possible configurations, then any such Turing machine either runs in time at most $k$, or it loops forever. That's because if it runs for at least $k+1$ time ...
D.W.♦
- 164k
7
votes
Accepted
What's after EXPSPACE?
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 ...
D.W.♦
- 164k
7
votes
Difference between auxiliary space v/s space complexity
First consider the definitions below:
$\mathbf{Auxiliary\space Space}$ is the temporary space allocated by your algorithm to solve the problem, with respect to input size.
$\mathbf{Space \space ...
- 1,659
7
votes
Accepted
Space complexity for storing integers in Python
It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the ...
- 1,339
7
votes
Accepted
What role does the lower bound play in the statement of Savitch's Theorem?
The proof relies on the following property: the time-complexity of a decider machine is at most exponential in its space-complexity. The bound assumptions, namely $f(n)\geq \log n$, are sufficient ...
- 4,775
6
votes
Accepted
Why do we reject turing machines that use space less than the log of the length of the input?
Consider any program in high-level language that has a loop going over all items:
for i from 1 to n
do something
end for
Implementing this loop takes $O(\log ...
- 279k
6
votes
Time complexity for count-change procedure in SICP
Order of growth of number of steps: $\theta (n^5)$
We can prove that, in general, the order of growth of number of steps is $\theta (n^m)$, where $m$ is the number of types of coin available. Here is ...
- 1,101
6
votes
Accepted
Understanding why ALL_nfa is in co-nspace
To show that $ALL_{\mathsf{NFA}}$ is in $\mathrm{co-NSPACE}(n)$, we must show that the complement $\overline{ALL_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$.
The complement is
$$\overline{ALL_{\...
- 2,516
6
votes
PSpace-completeness under PSpace reductions
Every language $X$ in PSPACE would be complete under your proposed definition, except for $\emptyset$ and $\Sigma^*$. You could reduce any PSPACE language $Y$ to $X$ by a reduction that ...
- 82.1k
6
votes
Why isn't an edge-map graph implementation used in practice?
Assume we are dealing with the representation of a weighted graph. I will use Python as the programming language to illustrate the points, which will remain true largely if another programming ...
- 39.1k
Only top scored, non community-wiki answers of a minimum length are eligible