Questions tagged [space-complexity]
Asymptotic analyses of the space needed to run algorithms.
508
questions
0
votes
0
answers
25
views
Variant of Generalized-Geography problem
Consider the "Generalized Geography" game: on directed graph G with selected start vertex, players take turns moving along edges, without ever going back to previously visited vertices. ...
- 43
2
votes
1
answer
23
views
I am struggling to define the space complexity of a turing machine
I have a problem where I have a class A which is made up of problems which is solveable with a TM with space complexity O(logn). I now need to prove that the problem, where an input string of length n ...
- 21
0
votes
0
answers
15
views
Why exactly does constructing a configuration graph of an $s(n)$ space bounded NDTM require that $s$ is space-constructible?
In "Computational Complexity: A Modern Approach", it states that to prove that $NSPACE(s(n))\subseteq DTIME(2^{O(s(n)})$, we can do the following:
By enumerating over all possible ...
0
votes
1
answer
36
views
In the proof that $DSPACE(S)\subseteq DTIME(2^{O(S)})$, why precisely do we require that $S=\Omega(\log n)$
I have read and understood various proofs, but have not been able to understand precisely why we require $S=\Omega(\log n)$.
1
vote
1
answer
47
views
Is "Length of Longest Increasing Subsequence" in L?
I can't find space complexity of this problem with search engines.
I think I have NL algorithm for it (just a basic "one by one non-deterministically accept values if possible"), but I ...
- 111
0
votes
1
answer
22
views
How can I reduce the complexity of an inverse DFT where I have a uniform frequency series being evaluated at non-uniform target points?
I have implemented an N-dimensional Non-Uniform Discrete Fourier Transform (in this case it's specifically an inverse NUDFT) using PyTorch. My goal with this implementation is to have a function which ...
- 101
1
vote
2
answers
33
views
Can a Code Script be Optimized for Time and Space Complexity Using Logic Gates
let's say that I have a Python script that performs various operations, including data manipulation, conditional logic, and iteration. However, I'm concerned about its time and space complexity ...
- 11
0
votes
2
answers
92
views
Is it possible to sort numbers in linear time and constant extra space?
The programming language is C++, and the elements of the input vector are of type int and able to take all valid ...
- 960
-4
votes
2
answers
86
views
PSPACE and Polynomial reduction
thanks for your help.
This is my first question, so I am very sorry for the bad presentation of the question.
I am studying computer science and this is the question I have been asked for the course ...
3
votes
1
answer
82
views
Is there a language $L$ such that $L \in DSPACE(1) \setminus DTIME(1)$?
It is a very straightforward question.
I know that the following holds, and I know why it holds:
$DTIME(f(n)) \subset DSPACE(f(n))$
However, is there a language $L \in DSPACE(1) \setminus DTIME(1)$? ...
- 133
2
votes
0
answers
67
views
Can a time-optimal algorithm have a time complexity better than its space complexity? [duplicate]
That's what I'm formally asking:
Let the algorithm $A$ have the worst-case time complexity $\Theta(f(n))$, such that for any algorithm $B$ with the worst-case time complexity $\Theta(g(n))$ doing the ...
- 51
0
votes
0
answers
34
views
Is TQBF problem where clauses are in 3-CNF format PSPACE-complete?
TQBF is a canonically PSPACE-complete problem. It consists of boolean formula such that all its variables are quantified. The question is whether a given TQBF instance is TRUE or FALSE.
https://en....
- 789
1
vote
1
answer
113
views
How to construct complement of NFA universality?
Given an input NFA, can one construct an NFA that is universal (that is, accepts all its inputs) if and only if, the input NFA isn't universal?
I tried to use the fact that NFA-universality is PSPACE-...
- 123
0
votes
1
answer
13
views
Transform OTM for Problem π to DTM ∈ DSPACE(n)
Given an Oracle Turing machine ($OTM$) that solves Problem π in max. 2n space, so $O(n)$ space and $O(n^2)$ time.
Is there a DTM that can solve $π$ in $O(n)$ space if time doesn't matter? (The length ...
- 11
2
votes
1
answer
71
views
Question about ALL-NFA in PSPACE
Here is the explanation in Sipser's. For step 3, why should we accept only when none of the markers lie on an accept state? If the alphabet of the language is $\Sigma = \{a,b,c\}$, and after the first ...
- 21
4
votes
1
answer
393
views
Read-once complexity of a matrix problem
Given a binary $n \times n$ matrix, we would like to decide whether there is a row or a column which consists entirely of $1$s. The caveat is that after we read an entry of the matrix, it is erased. ...
- 277k
2
votes
0
answers
18
views
Properties of $\mathsf{PH}[1]$ and $\Sigma^{\mathsf P}_{poly(n)}[1]$?
$\mathsf{PH}[1]$ is a variant of a polynomial hierarchy in which each machine can only call its oracle once. $\Sigma^{\mathsf P}_{poly(n)}[1]$ is a polynomially "tall" tower of $\mathsf{NP}[...
- 1,632
1
vote
1
answer
30
views
$NL$ Leaf languages and $PSPACE$
I am reading Papadimitriou's Computational Complexity and got stuck on part d) of the following exercise (pg. 505)
20.2.14 A panorama of complexity classes. ... A language $L \subseteq \{0, 1\}^*$ ...
- 13
0
votes
1
answer
43
views
Why is $DSPACE(\log^2n)\subseteq DTIME(n^{\log n})$?
I am having trouble with the statement that $DSPACE(\log^2n)\subseteq DTIME(n^{\log n})$ holds which is given without argument in the paper The structure and complexity of minimal NFA's over a unary ...
- 11
1
vote
0
answers
25
views
Auxiliary Space Complexity of Dictionaries whose Keys are Iterables of Variable Size
Recently, I began delving into complexity analysis with dictionaries. More specifically, I have been looking at auxiliary space complexity. For the most part, this type of analysis has been ...
- 11
4
votes
1
answer
120
views
What else measures are used to compare algorithm efficiency apart from Time and Space complexities?
While Time Complexity is the measure of how an algorithm scales with respect to input size, Space Complexity on the other hand measures how much the memory scales as input changes.
I see ...
0
votes
1
answer
71
views
How to allocate memory for prime numbers
I was working on an algorithm to find prime numbers, and I needed to allocate memory for each prime number that I found so far. I will do a search up to N and need to allocate all memory in advance. I ...
- 103
0
votes
1
answer
141
views
Isn't allocating a same size array for result considered to be space complexity O(n)?
It is related to this question: https://leetcode.com/problems/product-of-array-except-self/
And assuming we cannot alter the original array, but have to allocate a same size array to store the results,...
- 101
0
votes
1
answer
90
views
PSPACE≠co-NP?Is the statement true?
Is the statement in question true? how can i prove it formally?
I know that PSPACE=CO-PSPACE and NP ⊆ PSPACE and CO-NP ⊆ CO-PSPACE
0
votes
0
answers
17
views
$A\in LSPACE \Longrightarrow CYCLE(A)\in LSPACE$
Let $A$ be a language and define $$ CYCLE(A)= \{ yx | xy \in A \} $$ I need to prove, or disprove, $ A\in LSPACE \Longrightarrow CYCLE(A)\in LSPACE $.
First I tried to prove $CYCLE(A) \le_{L} A$ which ...
- 261
2
votes
1
answer
75
views
Lower Bound on Parity of Boolean Functions
Let's say we have boolean functions $f_1, \cdots, f_n$, each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show ...
- 23
2
votes
1
answer
81
views
Space efficient data structure to store precomputed All Nearest Neighbors in high dimensions
Seeking an indexing data structure that is smaller than quadratic in space.
As part of an NLP algorithm using word embeddings of 300-dimensions, I am trying to improve the speed of Word Mover's ...
- 261
2
votes
1
answer
192
views
ALL_{NFA} is PSPACE-complete
Show that $ALL_{NFA}$ = {$\langle M\rangle : M$ is $NFA$ and $L(M) = \Sigma^*$} is $\text{PSPACE-complete}$.
I've manged to prove that the langauge is in $\text{PSPACE}$.
Indeed, it is easy to see ...
- 21
1
vote
1
answer
310
views
Unions of PSPACE-comlete problems that are PSPACE-complete?
Let $A,B\subsetneq\Sigma^*$ be PSPACE-complete problems for some fixed $\Sigma$ such that $A\cup B\neq\Sigma^*$ and $A\cup B\in\mathrm{PSPACE}$. Does it follow that $A\cup B$ is PSPACE-complete?
In ...
5
votes
1
answer
75
views
Base transcoding with minimum storage and complexity
I want to reversibly transcode arbitrary information (a digital signature), initially $n$ bits, into symbols in an alphabet with $s$ symbols, with little space loss. In my application‡ $s=45$. Thus I ...
- 519
2
votes
0
answers
28
views
Are $\mathsf{L,NL}$ closed under reverse operation?
for a language $L$ we define $rev\left(L\right)=\left\{ \sigma_{n}\cdot\ldots\cdot\sigma_{1}\mid w=\sigma_{1}\cdot\ldots\cdot\sigma_{n}\in L\right\} $.
My question is, are $\mathsf{L,NL}$ closed under ...
- 161
2
votes
0
answers
55
views
Proving the language 2-SIMPLE-PATH is in NL
The Question
I define the language$$\mathsf{2-SIMPLE-PATH}=\left\{ \left\langle G,s,t\right\rangle \left|\begin{array}{c}
\mathsf{there\;are\;two\;different}\\
\mathsf{simple\;paths\;from}\;s\;\...
- 155
11
votes
5
answers
3k
views
Does an algorithm's space complexity include input?
Consider the Kadane's algorithm for finding maximum subarray within an array:
...
- 275
-3
votes
1
answer
59
views
NSPACE(n^2) and DSPACE(n^2) class problems [closed]
What problems belong in NSPACE(n^2) and DSPACE(n^2) class? Examples?
- 1
1
vote
2
answers
115
views
Order-preserving hashtable for integer tuples
There are integer tuples which index cells of a sparse multi-dimensional array (points inside n-parallelepiped), $n \le 32$.
The array itself is a BST with keys formed as $key = (...((a_0 * S_1 + a_1) ...
- 297
0
votes
4
answers
2k
views
What is the point of Bloom's filter if its false positive rate is so high?
This and this agree that there will be near 100% false positive rate with Bloom's filter should number of elements in the set ($n$) be greater than the number of bits in the filter ($m$).
E.g. if $n=...
- 115
2
votes
0
answers
32
views
How can we reduce the spatial complexity of intermediate indexes in relational databases at execution time?
In relational databases, what are the practical or theoretical ways to reduce the size and spatial complexity of intermediate indexes or tables* at execution time (so for example to reduce the size of ...
- 21
3
votes
3
answers
1k
views
A solution with O(n) time complexity is always slower than a solution with O(nlog(n)) time complexity even though they have the same space complexity
Why is Solution 1 faster than Solution 2?
The input passed to both solutions:
...
- 131
0
votes
0
answers
27
views
What will be the Computational Complexity in terms of order O of the operations shown in the following figure
Suppose I have L bits. First, I want to multiply the L bits with L orthogonal codes of length N, and then I want to add all the vectors.
So, first, I have to do a scalar multiplication with a vector ...
1
vote
1
answer
53
views
Confusion about NP vs. LINSPACE
I am working through Sipser, and have come accross the following claim, "any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$", which can be proven by looking at the upper ...
- 291
1
vote
1
answer
139
views
Why do we need to "allocate" an amount of space in the context of space-complexity?
In the chapter on space complexity in "Computational Complexity: A conceptual perspective" by Goldreich, it is stated (ch 5.1.2, p 146):
It
is tempting to say that sub-logarithmic space ...
- 3,752
1
vote
0
answers
14
views
How branching programs with small width are related to Turing machines with small space?
The complexity book by Arora and Barak mentions that "branching programs of constant width (reminiscent of a TM with O(1) bits of memory) seem inherently weak." I am not able to figure out ...
- 11
-4
votes
1
answer
86
views
what will be the space complexity of the following?
if two vectors are used for ex,
vector<vector> temp;
vector temp2;
then what will be the space complexity, will it be O(n) or O(n^2)?
1
vote
1
answer
100
views
Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?
Can every undirected graph be transformed into an equivalent graph (for the purposes of path-finding) with a maximum degree of 3 in logspace?
Given an undirected graph ...
- 401
2
votes
1
answer
226
views
Difference between "almost-linear" and "quasilinear" time complexities
In some works, such as the recent maxflow paper, there is reference to an "almost-linear" complexity, which typically refers to a complexity of $O(n^{1+o(1)})$.
This is similar to the notion ...
- 53
1
vote
1
answer
858
views
If every NP-hard language is PSPACE-hard then NP=PSPACE
To prove PSAPCE = NP we will show following inclusions :
NP $\subseteq$ PSPACE : If every NP-hard language is PSPACE-hard then
SAT is also PSPACE-hard. Since every language in PSPACE can be
reduced ...
1
vote
1
answer
216
views
A small issue regarding the proof of Savitch's Theorem
Savitch's Theorem states that $NSPACE\left( f \left( n \right)\right) \subseteq DSPACE\left( \left( f \left(n \right) \right)^2 \right)$ for any $f\left(n \right) \in \Omega \left( \log{n} \right)$.
...
2
votes
2
answers
55
views
Delete consecutive characters and add zeros at the end with a restriction
Given an array of characters, I need to delete all the characters that got repeated 3 or more times (consecutively) and add '0' at the end of the array for every deleted character,
The restrictions:
$...
- 21
0
votes
1
answer
126
views
Difficulty understanding the CANYIELD function in the Sipser text's proof of Savitch’s theorem
I was wondering whether someone could help me resolve an issue I have understanding the proof given for Savitch’s theorem in the Sipser text (3rd edition). The question I have is more or less ...
- 51
1
vote
1
answer
124
views
Implications of Savitch's theorem
I'm trying to figure out if the following statements are true:
• Savitch’s theorem implies that $NSpace(\log n)$ = $DSpace(\log n)$.
• Savitch’s theorem implies that $NSpace(n^2)$ = $DSpace(n^4)$.
• ...
- 443