# Questions tagged [space-bounded]

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

92 questions
Filter by
Sorted by
Tagged with
32 views

### Problem classes based on additional memory

Is there a classification of problems based on how much additional memory (other than input) they would need? For context: assume we have a multi-tape Turing machine $M$, with a bounded input tape and ...
298 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 ...
152 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 ...
• 43
244 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 ...
• 1,234
402 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 ...
176 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 ...
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 ...
• 13.2k
174 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 ...
• 73
224 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 ...
183 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. ...
• 1,469
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,...
• 421
1 vote
2k views

246 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 ...
• 393
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 ...
• 4,523
310 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
463 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$...
330 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,157
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 ...
• 4,731
124 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, ...
• 3,083
481 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?
• 528
564 views

• 19.1k
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 ...
• 19.1k
231 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 ...
• 455
202 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 ...
278 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-...
• 9,488
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 ...
• 19.1k
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 ...
242 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 ...
• 161
627 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
194 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?...
• 111
1k views

### Closure properties of deterministic context-sensitive languages

There does seem to be a lot of information regarding the closure properties of both deterministic context-free and nondeterministic context-sensitive languages. However, the literature is almost mute ...
• 189
1k 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 ...
• 19.1k
409 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 ...
• 53