Questions tagged [space-complexity]
The space-complexity tag has no usage guidance.
62
questions
0
votes
0answers
192 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 ...
3
votes
1answer
126 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 ...
3
votes
1answer
123 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 ...
1
vote
1answer
42 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 ...
4
votes
1answer
178 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?
4
votes
0answers
94 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 ...
0
votes
0answers
47 views
Size of CNF Formula for Adjacency in Configuration Graph
Suppose $M$ is a (non-deterministic) TM that runs in space $S(n)$. Then, the configuration graph $G_{M,x}$ of $M$ on $x$ has size $2^{O(S(n))}$. Arora-Barak (see http://theory.cs.princeton.edu/...
1
vote
0answers
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 ...
2
votes
0answers
175 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 $...
1
vote
0answers
110 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 ...
22
votes
12answers
2k 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? ...
3
votes
0answers
88 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 ...
6
votes
1answer
160 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 ...
19
votes
2answers
926 views
What is the space complexity of calculating Eigenvalues?
I am looking for a survey paper or a book covering results
about the space complexity of common linear algebra operations
such as matrix rank, eigenvalues calculation, etc.
I stress the "space ...
4
votes
1answer
189 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
vote
0answers
67 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}$...
0
votes
1answer
84 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 ...
1
vote
0answers
21 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 ...
6
votes
0answers
155 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 ...
1
vote
0answers
301 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 ...
3
votes
0answers
324 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 ...
2
votes
1answer
534 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 ...
3
votes
0answers
219 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)$?
2
votes
0answers
87 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 ...
8
votes
1answer
120 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 ...
7
votes
2answers
342 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 ...
11
votes
1answer
285 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 ...
4
votes
0answers
263 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} ...
5
votes
0answers
612 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 ...
2
votes
1answer
101 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 ...
4
votes
0answers
180 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 ...
0
votes
1answer
91 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 ...
5
votes
0answers
185 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 ...
1
vote
0answers
65 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 $...
6
votes
1answer
2k 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 $...
17
votes
1answer
945 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 ...
3
votes
1answer
268 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 ...
10
votes
1answer
296 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$ ...
21
votes
3answers
3k views
How much time to recognize palindromes in logarithmic space?
It is well-known that palindromes can be recognized in linear time on $2$-tape Turing machines, but not on single-tape Turing machines (in which case the time needed is quadratic). The linear-time ...
7
votes
0answers
169 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 $...
4
votes
1answer
750 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. ...
2
votes
1answer
261 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 ...
6
votes
0answers
364 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. ...
5
votes
0answers
845 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
votes
0answers
877 views
Does L=P imply any new complexity class separations?
If L=P then P is not equal to PSPACE. This follows from PSPACE properly containing L.
I am wondering if L=P implies any stronger separation between complexity classes? Does it imply P is properly ...
8
votes
2answers
345 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 ...
2
votes
1answer
322 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 ...
4
votes
1answer
236 views
Low space computation and branching program
One of the most elemental result of relationship between boolean circuit size and polynomial uniform computation is Pippenger and Fishers simulation: $DTIME[T(n)]\subseteq SIZE[T(n)\log T(n)]$.
I ...
22
votes
2answers
865 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 ...
1
vote
1answer
332 views
Does hyper-computational power of infinite time Turing machines also require infinite memory?
Can a infinite time Turing machine perform hyper-computation like checking the consistency of the set theory ZF without using infinite memory?
