19
votes
Accepted
Quadratic relationship between nondeterministic and deterministic space?
In my paper with Domaratzki and Kisman, "On the number of distinct languages accepted by finite automata with n states" published in J. Automata, Languages, and Combinatorics 7 (2002) we proved that ...
- 6,888
13
votes
How to prove that USTCONN requires logarithmic space?
The paper Counting Quantifiers, Successor Relations and Logarithmic Space, by Kousha Etessami proves that the problem $\mathbf{ORD}$ (which is essentially checking if a vertex $s$ precedes a vertex $t$...
- 2,267
12
votes
$BPL$ with polylog random bits is in $L$
It follows from this PRG of Nisan and Zuckerman. This paper shows that if you have an algorithm that uses space $S$ and only $\mathrm{poly}(S)$ random bits, then the number of random bits can be ...
- 5,055
11
votes
Accepted
Complexity class of efficient streaming algorithms
Along with my comment above (noting that not even AC0 is in "StreamL"), let me say that that this class has been studied before; you just need to know what they used to call it.
Search for "one-way ...
- 26.3k
11
votes
Accepted
Example of an context-sensitive language with a specific number of words of length $n$
The language
$$L=\bigcup_{n\in\mathbb N}\{0,1\}^{\lfloor n^\delta\rfloor}0^{n-\lfloor n^\delta\rfloor}$$
is computable in $\mathrm L\subseteq\mathrm{NSPACE}(n)=\mathrm{CSL}$, and it has $s_L(n)=2^{\...
- 14.8k
9
votes
Separating Logspace from Polynomial time
It made my day when my friend James told me that this thread from long ago was rekindled. Thank you for that.
Also, I had an urge to share some interesting references that are relevant to L vs Log(...
- 4,900
8
votes
How to iterate over vectors in order of probability in small space
The following gives an algorithm that uses approximately $2^n$ time and $2^{n/2}$ space.
First, let's look at the problem of sorting the sums of all subsets of $n$ items.
Consider this subproblem: ...
- 23.5k
8
votes
Separating Logspace from Polynomial time
[1] proves a lower bound for instances of mincost-flow whose bit-sizes are sufficiently large (but still linear) compared to the size of the graph, and furthermore proved that if one could show the ...
- 35.7k
7
votes
Separating Logspace from Polynomial time
this new paper was just highlighted by Luca Aceto in his blog as an EATCS best student paper at ICALP 2014 & has a novel way of separating NL/P:
Hardness Results for Intersection Non-Emptiness ...
- 10.8k
7
votes
Accepted
Do bounded-visit nondeterministic linear bounded automata recognize only regular languages?
A bit overkill, but:
this paper shows (among other nice things) that non-deterministic Hennie transducers realize exactly the class of non-deterministic MSO-definable transductions. The latter have ...
- 550
7
votes
Accepted
Does the space hierarchy theorem generalize to non-uniform computation?
One non-uniform "space hierarchy" that we can prove is a size hierarchy for branching programs. For a Boolean function $f: \{0, 1\}^n \to \{0, 1\}$, let $B(f)$ denote the smallest size of a branching ...
- 1,733
7
votes
Boolean circuits which correspond to L/poly
$\mathsf{L}/\mathrm{poly}$ can be characterized by polynomial size skew circuits. A boolean circuit is called skew if every AND-gate has at most one child that is not an input gate. Skew circuits and ...
- 4,501
6
votes
NFA to 2DFA: what are the upper and lower bounds?
The recent survey Two-Way Finite Automata: Old and Recent Results by Pighizzini states in the introduction:
The costs of the simulations of 1NFAs by 2DFAs and of 2NFAs by 2DFAs
are still unknown. ...
- 5,424
6
votes
Accepted
Time Hierarchies in DSPACE(O(s(n)))
This is an open problem: It is open whether $\mathrm{DTISP}(O(n \log n),O(n)) = \mathrm{DSPACE}(O(n))$ (or even $\mathrm{NSPACE}(O(n))$). We only know that $\mathrm{DTIME}(O(n))⊆\mathrm{DSPACE}(O(n/\...
- 2,237
6
votes
Accepted
Alternative to LBA for recognising context-sensitive languages
Here is an alternative model:
Benedek Nagy: Left-most derivation and shadow-pushdown automata for context-sensitive languages, ICCOMP'06: Proceedings of the 10th WSEAS international conference on ...
- 5,424
5
votes
Minimal encoding of a set (unordered collection of elements)?
What you're looking for is called a "succinct" or "implicit" dictionary. The best solution I know of is Backyard cuckoo hashing, by Arbitman et al from FOCS 2010, which "guarantees constant-time [...
- 11k
4
votes
Accepted
Satisfiability for various branching programs
For Q2:
For Ordered BDDs (OBDD) both satisfiability and counting solutions is polynomial in the size of the OBDD.
For indexed BDD, IBDD p. 16 satisfiability is NP-complete and the equivalence test ...
- 1,955
4
votes
Number of bits required for encoding variables with fixed sum?
Answer to question 1: $\left\lceil \log_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode the variables.
Proof: Count how many ways there are to choose $y_1,\ldots,y_r$ such that $y_i \ge 0$ ...
- 1,101
4
votes
How to iterate over vectors in order of probability in small space
We can do that in space $O(n)$ (if we don't care about the running time).
For a given string $x \in \{0,1\}^n$, we can compute in space $O(n)$ the number $r(x)$ of strings that are more likely than $...
- 3,844
4
votes
Closure properties of deterministic context-sensitive languages
Some results
Unless I am very mistaken, some of these questions are not hard. But I did not yet look at all of them.
I assume that a deterministic context-sensitive language (DCSL) is
defined as ...
- 1,502
4
votes
Is there a linear space lower bound for streaming set equality?
There are both deterministic lower bounds and randomized upper bounds (for a version of the problem where you get check-ins and check-outs in a single stream rather than check-ins in one stream and ...
- 50.2k
3
votes
Accepted
Can Quarter-Subset Membership be decided space-efficiently?
I assume from the discussion that you are not actually interested in work space as claimed, but in total space including the size of the input. (Otherwise the trivial $n$-bit encoding scheme can be ...
- 14.8k
3
votes
Is there a linear space lower bound for streaming set equality?
OK, so there are a lot of ways to store sets. I don't believe that any of them give you exactly what you want for the most general case, but here are several options.
Let $S_1$ and $S_2$ be the sets, ...
- 1,099
3
votes
Accepted
Best current space lower bound for SAT?
Looks like the best bound known (for multitape Turing machines) is logarithmic.
Suppose $\delta\log n$ bits of binary worktape is enough to decide whether any $n$-bit CNF formula is satisfiable, for ...
- 18.7k
3
votes
Accepted
Can multipebble automata decide all deterministic context-sensitive languages?
Perhaps you can build a language in DPSACE(n) that cannot be recognized by a MPA with $k=1$ using a diagonalization argument (probably the idea is similar to the one in Ben's answer, but I didn't dig ...
- 22.3k
3
votes
Can multipebble automata decide all deterministic context-sensitive languages?
No. Counterexample: the halting problem for MPAs is decidable in linear space: if the MPA has N states, we need |k|+2 bits of space to store the pebble locations, log N bits to store the current state ...
- 261
3
votes
Accepted
Why NL is not L
You are right in noticing that the state space of an NL machine is only polynomially large (i.e. the number of reachable states is polynomial in the length $n$ of the input). A deterministic Logspace ...
- 1,704
2
votes
Low space computation and branching program
Denoting the class of functions computed by branching programs of size $f(n)$ by $\text{BP}(f)$,
the best known bound seems to be the trivial $\text{DSPACE}(S(n)) \subseteq \text{BP}(2^{O(S(n))})$.
...
- 18.7k
2
votes
Best current space lower bound for SAT?
Perhaps we can prove a $\log n$ space lower bound for SAT in this way (but I'm not confident with limit/asymptotic analysis, so my answer can be totally wrong).
On a Turing machine model with one ...
- 22.3k
2
votes
Is there a linear space lower bound for streaming set equality?
If you can accept that no means no but yes means probably, you can do this in $O(\log n)$ bits of space, where $n$ is the number of bits in the sets.
To do so, first "collapse the universe" - use ...
- 11k
Only top scored, non community-wiki answers of a minimum length are eligible