The 2024 Developer Survey results are live! See the results

# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

517 questions
Filter by
Sorted by
Tagged with
1 vote
35 views

### Logarithmic space reduction from PATH to 2COLOR-PATH

2COLOR-PATH = {<G,s,t> | G is a 2-Colorable directed graph that has a directed path from s to t} I need to write a logarithmic space reduction from PATH to 2COLOR-PATH (explained above). I know ...
• 27
1 vote
17 views

### Does it count as auxiliary space if I overwrite the input-array?

Here is an example of what I mean: // input = [1,5,5,9,6,5] input = set(input) Would overwriting the input in such a way count as O(1) or O(n) auxiliary space? And ...
• 11
57 views

### How to prove a problem is EXP hard

Summary of the problem: Given an alternating time turing machine ($M$), a polynomial $p(.)$ and a string ($w$), is it EXPhard to find if $M$ accepts $w$ using not more than $p(|M|+|w|)$ space? My ...
1 vote
37 views

### Does modifying input space change space complexity?

The auxiliary space analysis that involves modifying the input array can lead to "unfair" situations. Examples: Consider that an algorithm that uses O(N) memory and does not need to ...
1 vote
42 views

### Do edge lists have O(E) storage if default values are used for absent keys?

Ordinarily, edge list representations of graphs take $O(V+E)$ space, where $V$ is the number of vertices and $E$ is the number of edges. For example, consider a graph with 5 nodes and a single edge ...
• 1,570
59 views

### Proof that $ALL_{DFA} \in SPACE(log^{2}n)$

we define $ALL_{DFA}$ as: $ALL_{DFA} = \{ <A> | \text{ A is a DFA and L(A) = }\Sigma ^ {*} \}$ I'm looking for a proof that $ALL_{DFA} \in SPACE(log^{2}n)$ where n is the number of states in the ...
• 77
1 vote
41 views

### Is there a lower bound on space complexity of non-in-place sorting?

There is a well known result stating that any comparison-based sorting algorithm has a time complexity of at least O(n log n). Selection sort and merge sort are two common examples, with time ...
• 123
42 views

### Relation between ExpTime vs Pspace

Are there any EXPTIME-COMPLETE problems that cannot be proven to be PSPACE-COMPLETE?
40 views

### What is the complexity of this tree recursive integer replacement algorithm?

LeetCode has an Integer Replacement problem defined as follows: Given a positive integer $n$, you can apply one of the following operations: If $n$ is even, replace $n$ with $n / 2$. If $n$ is odd, ...
• 1,570
65 views

### Does NSPACE($n^2$) $=$ DSPACE($n^4$)?

From Savitch's Theorem, we know that NSPACE($n^2$) $\subseteq$ DSPACE($n^4$), but does the other direction hold? As far as I understand all we can say is that DSPACE($n^4$) $\subseteq$ NSPACE($n^4$).
216 views

### Is TQBF in CNF is still PSPACE-complete

TQBF(Totally Quantified Boolean Formula) is a PSPACE-complete question. I wonder that if it restricted to CNF is still PSPACE-complete. TQBF-CNF means that the part following the quantifier is a CNF. ...
34 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
17 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 ...
39 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)$.
56 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 ...
• 245
37 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
36 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 ...
106 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 ...
• 990
90 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 ...
88 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
68 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 ...
• 53
38 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....
• 799
1 vote
128 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
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 ...
110 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
405 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. ...
• 278k
18 views

2k views

• 291
1 vote