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 ...
user avatar
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$...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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^{\...
user avatar
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(...
user avatar
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: ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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. ...
user avatar
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/\...
user avatar
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 ...
user avatar
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 [...
user avatar
  • 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 ...
user avatar
  • 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$ ...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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))})$. ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 11k

Only top scored, non community-wiki answers of a minimum length are eligible