Questions tagged [space-complexity]
The space-complexity tag has no usage guidance.
67
questions
3
votes
0
answers
162
views
Is $\mathsf{NP}\subseteq\mathsf{NSPACE}(n)$?
It is well-known that $\mathsf{P}\neq\mathsf{SPACE}(n)$, either for $\mathsf{SPACE}=\mathsf{DSPACE}$ or $\mathsf{NSPACE}$, and it is conjectured that both $\mathsf{P}\not\subseteq\mathsf{DSPACE}(n)$ ...
- 131
2
votes
0
answers
39
views
Space complexity of quantum algorithms for Subset sum
As far as I can find there are several quantum algorithms for the Subset sum problem with $2^{n/3}$ running time. Is there an algorithm with $2^{n/3}$ running time that uses much less space?
- 891
-1
votes
1
answer
86
views
How is memory being used by an algorithm, to define its space complexity? [closed]
In computation we always talk about the time and space complexity of a given algorithm. The time complexity describes how long an algorithm takes in relation to the quantity of input it receives. ...
- 99
7
votes
1
answer
315
views
Is $PSPACE$ believed to be different than $PP$?
From Googling, I couldn't find any discussion about whether $PP=PSPACE$ is more or less likely than $PP\subsetneq PSPACE$.
Is it currently believed that $PP\neq PSPACE$?
What would be the ...
- 215
7
votes
1
answer
414
views
Problem in the paper "Stable Minimum Space Partitioning in Linear Time"
The paper Stable Minimum Space Partitioning in Linear Time describes an algorithm that stably sorts a binary array (an array whose elements can only have two distinct values) in $O(n)$ time complexity ...
- 121
3
votes
1
answer
237
views
Detect if a graph has a $k$ cycle in space complexity $O((\log k)^d)$ for fixed $d \geq1$
For a graph $G$, I want to test if it contains a cycle of length $k$, for some $k$ much smaller than $|G|$. I am interested in particular in an algorithm with low space complexity. The cycle need not ...
- 133
1
vote
1
answer
72
views
Bipartite graph projections, with threshold
Let $G=(\top,\bot,E)$ be a bipartite graph: $E\subseteq \top\times\bot$.
The projections $G_\bot = (\bot,E_\bot)$ and $G_\top = (\top,E_\top)$ of $G$ are defined as follows: two vertices are linked ...
- 693
0
votes
0
answers
222
views
$CH=UL$ and partial breaking of transitive closure bottleneck problem and Savitch's theorem?
Let $L^t=DSPACE[O(\log n)^t]$, $NL^t=NSPACE[O(\log n)^t]$ and $UL^t=USPACE[O(\log n)^t$.
Savitch provides $NL\subseteq L^{2}$.
If $CH=UL$ we clearly got rid of the transitive closure bottleneck ...
- 12.8k
4
votes
1
answer
199
views
Is $UL\neq PSPACE$ known?
$L\neq DSPACE[\omega(\log n)]$ is known.
Is $UL\neq DSPACE[\omega(\log n)]$ and $UL\neq PSPACE$ known?
- 12.8k
4
votes
0
answers
119
views
Relationship between SC and NL
It is a major open problem whether $NL \subseteq SC$, or equivalently, whether directed reachability can be solved (simultaneously) in poly-logarithmic space and polynomial time. What is known ...
- 41
1
vote
0
answers
64
views
Reference to "compressibility" of logarithmic space [closed]
Is there a reference somewhere for the result SPACE($O(\log n)$) = SPACE($\log n$)? i.e. Big-O doesn't matter in logspace since you can compress the space. I feel like this is an elementary result but ...
- 21
1
vote
0
answers
122
views
Bounds on the construction of regular expressions' intersection operator
There are references on the exponential worst-case of the intersection operator for regular expressions (see [1]). However, I was wondering if there are similar results for the construction process ...
user59861
24
votes
12
answers
3k
views
What are some algorithms where space complexity tends to be the limiting factor in practice?
Time complexity can't be any lower than space complexity (at least one operation is required to use a unit of memory), so what are some algorithms where space actually tends to be the limiting factor? ...
- 401
3
votes
0
answers
336
views
Fastest known algorithm to enumerate k-cliques in a graph for fixed k
Is the best known algorithm for finding all $k$-cliques in a graph with $n$ nodes, for a fixed $k$, given by https://theory.stanford.edu/~virgi/combclique-ipl-g.pdf ?
The time-complexity of the ...
- 209
6
votes
1
answer
243
views
Is $L \subset 1NL$ when $L \neq NL$?
A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
- 119
3
votes
1
answer
220
views
Family of functions with properties similar to k-wise independent hash functions
I am looking for a family of functions that has similar properties to a family of $\ell$-wise independent hash functions. The goal is to hash $\ell$ pairwise different bit strings of length $k$ to a ...
- 183
4
votes
1
answer
262
views
On complexity class $\mathsf{\Pi_2 L}$
I suggest the following definition of $\mathsf{\Pi_2 L}$ (similarly to the certificate definition of $\mathsf{NL}$):
A language $L$ belongs to $\mathsf{\Pi_2 L}$ iff there exists a deterministic ...
- 1,973
1
vote
0
answers
80
views
Space complexity of global minimum cut
Are there any non-trivial bounds on the space complexity of global minimum cut? The problem is known to be in $\mathsf{RNC}$. Is anything known about containment in either $\mathsf{L}$ or $\mathsf{NL}$...
- 429
0
votes
1
answer
92
views
Question on deduction that a certain problem requires exponential space
My question concern's a statement from the classic paper The equivalence problem for regular expressions with squaring requires exponential space.
Regular expressions with squaring are like ordinary ...
- 2,037
1
vote
0
answers
26
views
Worst case polynomial in elimination theory under rank conditions?
Given $n$ polynomials $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})\in\mathbb Z[x_1,\dots,x_{2n}]$ where each of $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})$ is homogeneous of degree ...
- 12.8k
6
votes
0
answers
169
views
Immutable Space Model
I have heard it said that time is more precious than space because we can reuse space but not time. What if we treat space with this much reverence?
What is generally known about models of ...
- 4,258
1
vote
0
answers
325
views
EXPSPACE proof and its implications
I'm dealing with the min-max regret 0-1 Integer Linear Programming problem (MMR-ILP, for short), which is formulated as below.
\begin{equation} \label{eq:nip_obj}
\min_{x \in \Phi} \sum_{i = 1}^n ...
- 185
3
votes
0
answers
244
views
What is consequence of $PH\subseteq NSPACE((\log n)^2)$?
What is consequences of $PH\subseteq NSPACE((\log n)^2)$?
We don't even know PH is equals to L or not. I am wondering what will be happened when $PH\subseteq NSPACE((\log n)^2)$?
- 327
2
votes
0
answers
98
views
Simultaneous time-space complexity of directed reachability on bounded diameter graphs
Is directed reachability on a graph with bounded diameter (e.g. diameter $O(n^{1/2})$) known to be solvable simultaneously in polynomial time and sublinear space? Is anything known if the diameter is ...
- 429
2
votes
1
answer
542
views
What is best known space requrement for solving SATISFIABILITY problem in exp time
I searched a lot for finding best space requirement algorithm for SATISFIABILITY problem but I didn't find any thing better than brute force that is in DSPACE(n). is there exists better bound? and ...
- 327
5
votes
1
answer
297
views
Problems complete for non-deterministic PSPACE
Savitch's theorem, i.e. the fact that $NSPACE(f(n)^2) \subseteq DSPACE(f(n)^2)$ implies PSPACE = NPSPACE.
Using the idea of Savitch, Sipser proves in his lectures that TQBF is PSPACE-complete.
What ...
- 94
3
votes
0
answers
189
views
Is $SUBLOG\subset DTIME(n)$?
In the course of trying to give a more natural answer to a previous question of mine involving the complexity classes $$SUBLOG=\{L\mid L \text{ is recognizable by a sublogarithmic-space TM} \}$$ and $...
- 643
7
votes
2
answers
384
views
Are space and time hierarchies even comparable?
I am wondering if there are any results to what extent the space and time hierarchies "disagree" on which problem is harder. For example, is it known whether there are languages $L_1$ and $L_2$ such ...
- 643
11
votes
1
answer
321
views
Does the space hierarchy theorem generalize to non-uniform computation?
General Question
Does the space hierarchy theorem generalize to non-uniform
computation?
Here are a few more specific questions:
Is $L/poly \subsetneq PSPACE/poly$?
For all space ...
- 5,127
4
votes
0
answers
286
views
The problem of whether or not every function computable in time $T(n)$ is computable in time $T(n)^{O(1)}$ and space $T(n)^{o(1)}$ simultaneously
If a function is computable in time $T(n)$, is it computable in time $T(n)^{O(1)}$ and space $T(n)^{o(1)}$ simultaneously?
We won't be able to prove it, because it implies the open problems $\text{P} ...
- 548
5
votes
0
answers
897
views
What happens when PSPACE contains NEXP?
The complexity class NEXP is defined as the set of all languages that an arbitrary nondeterministic exponential time Turing Machine accepts (i.e. NTIME($2^{p(n)}$) for $p()$ a polynomial).
In the ...
- 51
3
votes
0
answers
370
views
Complexity of the mandelbrot set on rationals
(Also posted on mathoverflow) Given two rationals $a,b \in \mathbb{Q}$, call $c = a + ib$, i.e., the complex number represented by these two rationals.
A point $c$ is contained within the Mandelbrot ...
- 1,132
2
votes
1
answer
128
views
Is sliding blocks linear space complete?
Sliding blocks is PSPACE complete even in its simplest form involving 1x2 and 2x1 blocks (without rotation or fractional positions) in a rectangular area, with goal being to move a designated block to ...
- 2,537
4
votes
0
answers
197
views
Is there a language in NSPACE(O(n)) and (very likely) not in DSPACE(O(n))?
Actually I found that the set of context-sensitive Languages,
$\mathbf{CSL}$ ($\mathbf{=NSPACE}(O(n))$ $= \mathbf{LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular ...
- 151
0
votes
1
answer
102
views
Complexity status of restricted k-clique [closed]
Restricted $k$-clique:
Input: $(G,v,k)$ where $v$ is vertex in $V$
Output: k-clique containing vertex $v$.
What is the space and time complexity status of this Restricted $k$-clique problem?
Is ...
- 175
5
votes
0
answers
230
views
On space complexity of permanent modulo $2^t$?
We know from here that permanent of $0/1$ matrix modulo $2^t$ is in $DTIME(n^{t+3})$ and hence in $P$. My question is whether permanent of $0/1$ matrix modulo $2^t$ is in $L$ as well or is the current ...
- 12.8k
1
vote
0
answers
71
views
parametrized logspace algorithm for k-dominating set for planar graphs
$k$-Dominating set:
Given a graph $G=(V,E)$ where $V$ is a set of vertices and $E$ a set of edges, and an integer $k$, the $k$-Dominating set problem determines if there exists a subset of vertices $...
- 175
17
votes
1
answer
965
views
Quadratic relationship between nondeterministic and deterministic space?
Savitch's theorem shows that $\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)$ for all large enough functions $f$, and proving that this is tight has been an open problem for decades.
Suppose ...
- 18.9k
10
votes
1
answer
333
views
Is bounded-width SAT decidable in logspace?
Elberfeld, Jakoby, and Tantau 2010 (ECCC TR10-062) proved a space-efficient version of Bodlaender's theorem.
They showed that for graphs with treewidth at most $k$, a tree decomposition of width $k$ ...
- 18.9k
6
votes
1
answer
4k
views
k-Vertex Cover problem is in parameterized Log space
$k$-Vertex Cover:
Given a graph $G = (V, E)$ where $V$ is a set of vertices and $E$ a set of edges, and an integer $k$,
the $k$-Vertex Cover problem determines if there exists a subset of vertices $...
- 175
4
votes
1
answer
393
views
Space complexity of integer programming
Given $A\in\Bbb Z^{n\times k}$, $v\in\Bbb Z^n$ and variables $x_1,\dots,x_k$ given as a vector $x$ we know that solving $x\in\Bbb Z^k$ in $Ax\leq v$ is fixed parameter tractable. There is a ...
- 12.8k
7
votes
0
answers
197
views
Range min-gap query
The min-gap of an array $A[1..n]$ of $n \ge 2$ elements is defined as $\min_{1 \le i < j \le n}{|A_i - A_j|}$. Now, I am considering a query version of it. Given $A$, a query receives two integers $...
- 71
8
votes
1
answer
125
views
Can Quarter-Subset Membership be decided space-efficiently?
Consider the following decision problem.
Let $q = \sum_{i=0}^{n/4} \binom{n}{i}$ and let $(C_0^n, C_1^n,\dots,C_{q-1}^n)$ be a suitable enumeration of those subsets of $\{0,1,\dots,n-1\}$ that have at ...
- 18.9k
4
votes
1
answer
991
views
Space complexity for multiplying $m$ matrices
Suppose you have $m$ $n$ by $n$ matrices $M_1,M_2,\dotsc,M_m$, and you want to calculate their product $\prod_{i=1}^{m} M_i$.
The naive method use $m \cdot poly(n)$ times but needs $poly(n)$ memory. ...
- 176
2
votes
1
answer
346
views
Space requirements for solving True Quantified Boolean Formulas problem [closed]
I came across this section on the wikipedia page for the TQBF solving problem, and just can't wrap my head about the fact that the space requirement is linear. Moreover, it does not provide any ...
- 133
6
votes
0
answers
421
views
PSPACE completeness, with different kinds of reductions
PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. ...
- 161
5
votes
0
answers
1k
views
Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L
It would be nice to show that $P=L$ implies $NP=NL$. Or, $NP=NL$ implies $UP=UL$. Or maybe, $⊕P = ⊕L$ implies $PP = PL$.
Are there any known connections between the problems: P vs L, UP vs UL, NP ...
- 5,127
8
votes
2
answers
353
views
The hardness of generating an instance of a problem that is harder than the complexity of the resulting problem
In the movie Inception Cobb asks a asks Ariadne to design a maze that takes twice as much time to design. This lends itself to a generalized problem where we have an situation where we are resource ...
- 1,641
2
votes
1
answer
398
views
What is the space complexity of CTL model checking?
What is the space complexity of the CTL model checking algorithm via labeling without fairness (see e.g. Model Checking by Clarke at al Section 4.1 or Principles of Model Checking by Baier et al ...
23
votes
2
answers
989
views
Best current space lower bound for SAT?
Following on from a previous question,
what are the best current space lower bounds for SAT?
With a space lower bound I here mean the number of worktape cells used by a Turing machine which uses a ...
- 18.9k