Questions tagged [space-bounded]
Questions about space resources of computations in computational complexity or algorithms.
88
questions
4
votes
1
answer
103
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,204
14
votes
1
answer
373
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 ...
- 818
5
votes
1
answer
171
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
133
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 ...
- 12.8k
7
votes
1
answer
170
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
7
votes
1
answer
214
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 ...
- 862
10
votes
0
answers
167
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,439
3
votes
0
answers
110
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
2
answers
1k
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($\...
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
5
votes
1
answer
267
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}/\...
- 689
9
votes
1
answer
222
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 ...
- 383
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 ...
- 4,439
5
votes
1
answer
303
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
4
votes
1
answer
445
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$...
- 635
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
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 ...
- 4,681
2
votes
0
answers
121
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,033
3
votes
1
answer
466
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?
- 516
12
votes
1
answer
526
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}...
- 59
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
4
votes
1
answer
131
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 ...
- 2,799
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 ...
- 2,151
4
votes
0
answers
133
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}$?
- 51
5
votes
6
answers
485
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 ...
- 3,950
2
votes
1
answer
406
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 ...
- 1,973
13
votes
0
answers
389
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 $\...
- 18.9k
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
9
votes
1
answer
225
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
5
votes
0
answers
192
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 ...
user6973
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-...
- 9,438
20
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 ...
- 18.9k
0
votes
1
answer
124
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
237
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
7
votes
0
answers
599
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$-...
user6973
1
vote
0
answers
184
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
5
votes
1
answer
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
23
votes
2
answers
991
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
5
votes
1
answer
397
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
3
votes
1
answer
301
views
Number of bits required for encoding variables with fixed sum?
Assume we'd like to be able to encode variables $x_1,x_2,\cdots,x_r\in \mathbb{N}$, such that $\forall i\in[r]:1\leq x_i\leq N$ and $$\sum_{i=1}^{r}x_i=M$$
It's easy to store the variables using $r\...
- 9,438
4
votes
2
answers
368
views
Minimal encoding of a set (unordered collection of elements)?
Assume you have universe $\mathcal{U}=\{e_1,e_2,\ldots e_N\}$.
If we like to encode an ordered sequence of $k$ elements from $\mathcal{U}$, it's not hard to argue that $k\log |\mathcal{U}|$ bits are ...
- 9,438
11
votes
3
answers
495
views
How to iterate over vectors in order of probability in small space
Consider an $n$ dimensional vector $v$ where $v_i \in \{0,1\}$. For each $i$ we know $p_i = P(v_i = 1)$ and let us assume the $v_i$ are independent. Using these probabilities, is there an efficient ...
- 3,950
4
votes
1
answer
278
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 ...
- 49
21
votes
1
answer
442
views
Can $\{a^nb^n\}$ be recognized in poly-time probabilistic sublogarithmic-space?
Consider language $ \mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \} $.
It is known that $ \mathtt{EQUALITY} $ cannot be recognized by any sublogarithmic-space alternating Turing machine (ATM) (...
- 3,707
13
votes
0
answers
427
views
Non-deterministic logspace with two-sided error
The class BPL is the set of all problems solvable by a Turing machine running in logarithmic space and polynomial time with two-sided error; that is, if $x\in L$ then the machine accepts with ...
- 1,224
8
votes
1
answer
329
views
Storing a bit vector in uninitialized memory and minimal space
A well-known trick for storing bit vectors using uninitialized memory can allocate a bit vector of size $n$ in which all of the bits are set to $0$ by allocating $(2 n + 1)\lceil \lg n \rceil$ bits of ...
- 11.2k
6
votes
1
answer
185
views
How big is NSC^k?
It is well known that $\mathsf{NL} \subseteq \mathsf{NC} \subseteq \mathsf{P}$, both inclusions conjectured to be proper. On the other hand $\mathsf{NP} \supseteq \mathsf{P}$, also probably a proper ...
- 2,151
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 ...
- 241
1
vote
1
answer
235
views
Super-logspace mapping reducibility
There are two well-known mapping reducibilities: polytime and logspace. In both cases, the length of the output string can be at most polynomial in the length of a given input string. If we allow to ...
- 3,707
12
votes
2
answers
363
views
Can multipebble automata decide all deterministic context-sensitive languages?
A MPA (multipebble automaton) is a 2DFA (two-way deterministic finite automaton) that can use arbitrary number of pebbles (actually at most $ |w|+2 $ pebbles on a given input $ w $ - the input is ...
- 3,707