Skip to main content

Questions tagged [space-bounded]

Questions about space resources of computations in computational complexity or algorithms.

Filter by
Sorted by
Tagged with
5 votes
1 answer
208 views

Polylog-space vs NP

Let $\text{polyL} = \cup_{c} \text{SPACE}[\log^c n]$ be the set of all problems that can be solved using polylog space, what is known/believed about its relation with NP? And perhaps even PP? I'm ...
4 votes
1 answer
171 views

Implicit characterization of sublogarithmic space

Let $SUBLOG = DSPACE(o(\log(n)) \setminus DSPACE(O(1))$ be the set of languages decidable with less than logarithmic space, but more than a constant amount of space, on a multi-tape Turing machine ...
4 votes
1 answer
138 views

Intersection Non-Emptiness for Two-Way Finite Automata

We know that checking the emptiness of intersection of an unbounded number of deterministic finite automata is PSpace-complete, and that just the emptiness problem for a nondeterministic two-way ...
11 votes
1 answer
530 views

Connection between PCP and L=SL

The book by Arora and Barak contains in chapter notes on PCP We note that Dinur's general strategy is somewhat reminiscent of the zig-zag construction of expander graphs and Reingold's ...
5 votes
1 answer
308 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 ...
14 votes
2 answers
1k views

Space alternating hierarchy

It is known thanks to Immerman and Szelepcsényi that ${\rm NSPACE}(f)={\rm coNSPACE}(f)$ if $f=\Omega(\log)$ (even for non-space constructible functions). In the same paper, Immerman state that the ...
14 votes
1 answer
2k views

Is CFL strictly contained in NL?

We know that $\mathsf{REG}=\mathsf{NSPACE}(O(1))$ and $\mathsf{CSL}=\mathsf{NSPACE}(O(n))$. What is the relation of $\mathsf{CFL}$ and $\mathsf{NSPACE}(O(\log n))=\mathsf{NL}$? Is $\mathsf{CFL}$ a ...
14 votes
1 answer
398 views

What is (a reasonable conjectured lower bound on) the query complexity of solving an $n\times n$ system of linear equations given space $O(n)$?

I am faced with the following problem: A uniformly random $n \times n$ matrix $M$ over a finite field $\mathbb{F}$ is sampled. The algorithm has oracle access to the matrix entries, and each query to ...
17 votes
2 answers
825 views

SC^2 algorithms for st-connectivity

Savitch gave a deterministic algorithm to solve st-connectivity using $O({\log}^2{n})$ space, implying $NL \subseteq DSPACE({\log}^2{n})$. Savitch’s algorithm runs in time $2^{O({\log}^2{n})}$. It is ...
17 votes
1 answer
400 views

Which results make quantum space interesting?

Time-bounded quantum computation is obviously very interesting. What about space-bounded quantum computation? I know many interesting results for quantum computation with sublogarithmic space bounds ...
5 votes
1 answer
173 views

Alternative to LBA for recognising context-sensitive languages

I've always felt that there's no "canonical" automata for recognising context-sensitive languages. Much like there's DFA for regular, PDA for context-free and Turing machines for RE. I'm ...
0 votes
1 answer
136 views

Derandomizing arbitrary width *read-many* and *ordered* branching programs?

Modifying following TedP We know that derandomizing width $5\leq k\in O(1)$ read many branching programs is equivalent to $BPNC^1=NC^1$ and derandomizing width $k\in\Omega(n)$ read once ordered ...
7 votes
1 answer
173 views

Example of an context-sensitive language with a specific number of words of length $n$

Let $s_L(n)$ denote the number of words of length $n$ in $L$. For context-free languages it is known that $s_L(n)$ is either polynomial or exponential. For context-sensitive languages this is probably ...
21 votes
1 answer
1k views

How to prove that USTCONN requires logarithmic space?

USTCONN is the problem that requires deciding whether there is a path from the source vertex $s$ to the target vertex $t$ in a graph $G$, where these are all given as part of the input. Omer Reingold ...
11 votes
0 answers
2k views

Which algorithm can do a stable in-place binary partition with only O(N) moves?

I'm trying to understand this paper: Stable minimum space partitioning in linear time. It seems that a critical part of the claim is that Algorithm B sorts stably a bit-array of size n in O(nlog2n) ...
7 votes
1 answer
221 views

Complexity class of efficient streaming algorithms

Consider the class of problems $\mathsf{StreamL}$ which can be solved in logarithmic space reading the input in a single pass from left to right. In other words: $L \in \mathsf{StreamL}$ if there ...
34 votes
2 answers
1k views

Does LOGLOG = NLOGLOG?

Define LOGLOG as the class of languages which can be computed in space O(loglog n) by a deterministic Turing machine (with two-way access to the input). Similarly define NLOGLOG as the class of ...
10 votes
0 answers
178 views

Alternative proofs of Savitch's theorem?

Question: Are there any known proofs of Savitch's theorem that $NL \subseteq L^2$ besides the usual one? By the usual one I mean the proof based on recursively querying whether there is a midpoint. ...
3 votes
0 answers
111 views

The number of words of length $n$ in a context-sensitive language

Let $L$ be a context-sensitive language, $s_{L}(n)$ is denoted by the number of words of length $n$ in $L$. What is known about $s_{L}(n)$? Note that it is known that $s_{L}(n)$ is either polynomial,...
1 vote
2 answers
2k views

Why NL is not L

I'm a beginner in learning complexity and get confused at NL. NL is the class of languages that are decidable in logarithmic space on a nondeterministic Turing machine. In other words, NL = NSPACE($\...
5 votes
6 answers
491 views

Is there a linear space lower bound for streaming set equality?

Consider two streams. In each stream one string arrives at a time. A query asks: Is the set of strings that has arrived so far the same in both streams? Is there a linear space randomized lower ...
0 votes
1 answer
94 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 ...
5 votes
1 answer
277 views

Boolean circuits which correspond to L/poly

Branching programs are usually used as a computation model for non-uniform logarithmic space $\mathsf{L}/\mathrm{poly}$. Is there a reference about Boolean circuits corresponding to $\mathsf{L}/\...
10 votes
1 answer
240 views

$BPL$ with polylog random bits is in $L$

Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$. My question is ...
5 votes
0 answers
119 views

Reduction between functions that preserves time and space-complexity

Under which reduction(s) is the class $\mathsf{FTISP}(t(n), s(n))$ closed? Let $\mathsf{FTISP}(t(n), s(n))$ the class of functions from $\{0,1\}^*$ to itself that are computable by a Turing machine ...
8 votes
1 answer
126 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 ...
13 votes
0 answers
396 views

Consequences of bipartite perfect matching not in NL?

Are any significant consequences known of $\text{BPM} \not\in \textsf{NL}$? I'm interested in the status of the following well-studied decision problem, in particular whether it is known to be in $\...
4 votes
1 answer
460 views

Converting Kuroda normal form rules to the Penttonen normal form

Let us say we have some abstract context-sensitive grammar in the Kuroda normal form, which is where all production rules are of the form: $AB\rightarrow CD$ or $A\rightarrow BC$ or $A\rightarrow B$...
11 votes
1 answer
329 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 ...
3 votes
0 answers
33 views

references for optimal computation under memory constraint?

Can someone help me find some references for finding good execution schedule given memory constraint? Assuming computation graph is simple in some sense (ie, small tree-width) There is this reference ...
3 votes
1 answer
479 views

NFA to 2DFA: what are the upper and lower bounds?

Suppose that one has an NFA (from, say, a regular expression). What is the state complexity of turning it into a 2DFA?
2 votes
0 answers
122 views

Is scalable hardware support for LogCFL (= sAC^1) possible?

The (uniform) circuit classes $TC^0$, $NC^1$ and $sAC^1$ seem to lend themselves to efficient hardware implementation. But using an FPGA approach to create the circuits on the fly seems problematic, ...
12 votes
1 answer
552 views

Time Hierarchies in DSPACE(O(s(n)))

The time hierarchy theorem states that turing machines can solve more problems if they have (enough) more time. Does it hold in some way if the space is limited asymptotically? How does $\textrm{DTISP}...
17 votes
1 answer
971 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 votes
1 answer
941 views

Completeness and Context-Sensitive Languages.

I'm interested in two questions regarding context-sensitive languages (CSL) and completeness: Is there a notion of completeness for CSL, and which languages are complete? Are there natural CSL that ...
4 votes
1 answer
134 views

Base extension in residue number systems with low space

Suppose I have a number $x$ represented in a residue number system, so $x = (x_1, \ldots, x_m)$, where $x_i \equiv x \pmod{p_i}$, and the $p_i$'s are all relatively prime (they can be distinct primes ...
1 vote
0 answers
52 views

Circuit games in extensive form with imperfect information

Consider $l,m,n,N \in \mathbb{N}$ and circuits $C: \{0,1\}^{l+m} \rightarrow \{0,1\}^l$, $D: \{0,1\}^{l+n} \rightarrow \{0,1\}^l$. Consider the following zero-sum two-layer extensive-form game with ...
4 votes
0 answers
134 views

Is there a certificate definition for polyL?

Arora explained in his book a certificate definition for $\mathsf{NL}$ using a read-once tape. Can we apply a similar definition for the class $\mathsf{polyL}$?
3 votes
1 answer
418 views

Can every distribution producible by a probabilistic PSpace machine be produced by a PSpace machine with only polynomially many random bits?

Let $M$ be a probabilistic Turing machine with a unary input $n$ whose space is bounded by a polynomial in $n$ and its output is a distribution $D$ over binary strings. Note that the number of ...
26 votes
3 answers
845 views

Intermediate problems between L and NL

It is well-known that directed st-connectivity is $NL$-complete. Reingold's breakthrough result showed that undirected st-connectivity is in $L$. Planar directed st-connectivity is known to be in $UL \...
22 votes
3 answers
582 views

space-bounded TMs and oracles

In general, the query-tape for an oracle counts towards the space-complexity of a TM. However, it seems plausible to allow a write-only oracle-tape (such as is used in L-space reductions). Is such a ...
5 votes
0 answers
199 views

Is anything known about Sokoban with only 1 box?

This is intended to be a simpler version of my earlier question here. In this post, 1-Sokoban-search is Sokoban with only 1 box, 1-Sokoban-decision is the corresponding decision problem, and 1-Sokoban ...
15 votes
2 answers
1k views

Quantum analogues of SPACE complexity classes

We often consider complexity classes where we are bounded in the amount of space our Turing machine can use, for example: $\textbf{DSPACE}(f(n))$ or $\textbf{NSPACE}(f(n))$. It seems that early in ...
9 votes
1 answer
228 views

Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?

Do bounded-visit nondeterministic linear bounded automata recognize only regular languages? By a nondeterministic linear bounded automaton (nLBA) I mean a single-tape nondeterministic Turing machine ...
14 votes
1 answer
307 views

Machine characterization of $SAC^i$

$SAC^i$ is the class of decision problems solvable by a family of $O({\log}^i{n})$ depth circuits with unbounded-fanin OR and bounded-fanin AND gates. Negations are only allowed at the input level. It ...
7 votes
0 answers
277 views

Integer queue summation

As part of a project I'm working on, we came up with an efficient algorithm for approximating the sum of an integers queue. The setting is as follows: Let $\epsilon>0$. we need to maintain a space-...
0 votes
1 answer
125 views

An algorithm for counting to Graham’s Number

I’m trying to come up with an algorithm that performs some action a Graham’s number of times on a machine with a reasonable amount of memory. I thougth of the way to organize counter suitable for ...
6 votes
0 answers
241 views

What is the space complexity of computing the eigenvectors of a matrix?

By the answer to this question, computing the eigenvalues of a matrix to within $2^{-n}$ precision can be done in polylogarithmic space. Is it also possible to compute the eigenvectors of a matrix to ...
7 votes
0 answers
624 views

complexity of Sokoban with a small number of boxes

(I asked a very concise version of this one month ago on cs.stackexchange, and although it got edited, it was not (otherwise) responded to.) In this post, for positive integer values $k$, "$k$-...
1 vote
0 answers
189 views

What is the minimal known space for polytime algorithms

Let L be a language whose minimal running time is $O(n^k)$ do we know of any bounds on the minimal amount of space necessary to compute L other than the trivial $n^k$? Are there any conjectured bounds?...