# Questions tagged [space-complexity]

The tag has no usage guidance.

62 questions
Filter by
Sorted by
Tagged with
321 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 ...
173 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 ...
1 vote
57 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 ...
208 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 ...
188 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?
104 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 ...
1 vote
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 ...
1 vote
116 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 ). However, I was wondering if there are similar results for the construction process ... 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? ...
136 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 ...
180 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 ...
152 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 ...
223 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
75 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}$...
85 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
22 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 ...
161 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
314 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 ...
230 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)$?
90 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 ...
539 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 ...
182 views

745 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 ...
353 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 ...
110 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 ...
190 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 ...
99 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 ...
200 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
67 views

377 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 ...
186 views

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 $... 8 votes 1 answer 122 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 ... 4 votes 1 answer 915 views ### Space complexity for multiplying$m$matrices Suppose you have$mn$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 1 answer 306 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 0 answers 384 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 0 answers 924 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 ... 8 votes 2 answers 352 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 1 answer 365 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 952 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 1 answer 343 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? 4 votes 1 answer 361 views ### Satisfiability for various branching programs Clearly, SAT for CNF, formula, or many classes of boolean circuits have strong significance on the entire theory community. Branching program, or BDD is one of the most basic and popular computational ... 8 votes 0 answers 339 views ### Linear space language that requires exponential time without ETH The$\mathsf{P} \neq \mathsf{PSpace}$conjecture means that There is a language$L \in \mathsf{DSpace}(O(n^t))$for some$t>0$such that for all positive integers$k$,$L$requires$\Omega(n^k)...
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 ...
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 ...