Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
0 votes
0 answers
29 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. ...
Anuj's user avatar
  • 43
2 votes
1 answer
25 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 ...
Lex's user avatar
  • 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 ...
BreadthFirstTreeSearchFan's user avatar
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)$.
BreadthFirstTreeSearchFan's user avatar
1 vote
1 answer
48 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 ...
Noone AtAll's user avatar
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 ...
kairocks2002's user avatar
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 ...
edge selcuk's user avatar
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 ...
Zirui Wang's user avatar
-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 ...
Lior klunover's user avatar
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)$? ...
ampersander's user avatar
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 ...
sbh's user avatar
  • 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....
J.Doe's user avatar
  • 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-...
NooneAtAll3's user avatar
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 ...
Theorynoob's user avatar
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 ...
Bryzem's user avatar
  • 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. ...
Yuval Filmus's user avatar
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}[...
rus9384's user avatar
  • 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\}^*$ ...
KJL's user avatar
  • 13
0 votes
1 answer
44 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 ...
Yannik Eik's user avatar
1 vote
0 answers
26 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 ...
LateGameLank's user avatar
4 votes
1 answer
121 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 ...
PolamreddyVivekReddy's user avatar
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 ...
Jip Helsen's user avatar
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,...
Stefanie Gauss's user avatar
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
user161390's user avatar
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 ...
CforLinux 's user avatar
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 ...
dino-t's user avatar
  • 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 ...
Paul Chernoch's user avatar
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 ...
GeoArt's user avatar
  • 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 ...
Daniil Kozhemiachenko's user avatar
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 ...
fgrieu's user avatar
  • 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 ...
Ariel Yael's user avatar
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\;\...
snatchysquid's user avatar
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: ...
Eugene Yarmash's user avatar
-3 votes
1 answer
61 views

NSPACE(n^2) and DSPACE(n^2) class problems [closed]

What problems belong in NSPACE(n^2) and DSPACE(n^2) class? Examples?
ZlyVlk's user avatar
  • 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) ...
Andrey Godyaev's user avatar
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=...
caveman's user avatar
  • 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 ...
Heiz's user avatar
  • 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: ...
DeyaEldeen's user avatar
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 ...
Pankaj Singh's user avatar
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 ...
user918212's user avatar
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 ...
user56834's user avatar
  • 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 ...
CSNU's user avatar
  • 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)?
Shruthi Mohan's user avatar
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 ...
Jesus is Lord's user avatar
2 votes
1 answer
232 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 ...
aghx99's user avatar
  • 53
1 vote
1 answer
861 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 ...
False Equivalence's user avatar
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)$. ...
Benicio Agüero's user avatar
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: $...
chucha's user avatar
  • 21
0 votes
1 answer
127 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 ...
SGR's user avatar
  • 51
1 vote
1 answer
125 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)$. • ...
SVMteamsTool's user avatar

1
2 3 4 5
11