Skip to main content
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 ...
Jeffrey Shallit's user avatar
13 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 ...
Or Meir's user avatar
  • 5,615
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^{\...
Emil Jeřábek's user avatar
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 ...
Ryan Williams's user avatar
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 ...
Jan Johannsen's user avatar
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 ...
William Hoza's user avatar
  • 1,743
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. ...
Hermann Gruber's 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/\...
Dmytro Taranovsky's 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 ...
Hermann Gruber's user avatar
6 votes
Accepted

Intersection Non-Emptiness for Two-Way Finite Automata

Unlike one-way models, intersection of 2-way NFAs is "cheap": Given 2-way NFAs $A_1,A_2$, you can construct a 2-way NFA $B$ for their intersection that works as follows: it first behaves ...
Shaull's user avatar
  • 5,656
4 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 ...
Lieuwe Vinkhuijzen's user avatar
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 ...
David Eppstein's user avatar
4 votes

Problems complete for non-deterministic PSPACE

A class that was more familiar at the time than NPSPACE was the class of context-sensitive languages. Let CSL denote the set of context-sensitive languages. By Kuroda's theorem (1960), this set is ...
Hermann Gruber's 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 ...
Emil Jeřábek's 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, ...
bbejot's user avatar
  • 1,099
2 votes
Accepted

Base extension in residue number systems with low space

By a result of Chiu, Davida, and Litow [1], improved by Hesse, Allender, and Barrington [2], Chinese remainder representation base extension is computable in logarithmic space, and in fact in DLOGTIME-...
Emil Jeřábek's 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 ...
jbapple's user avatar
  • 11.2k
2 votes

Converting Kuroda normal form rules to the Penttonen normal form

You can find the proof in Penttonen's original research article: Martti Penttonen, One-Sided and Two-Sided Context in Formal Grammars. Information and Control 25, pp. 371-392 (1974). https://doi.org/...
Hermann Gruber's user avatar
2 votes

Why NL is not L

People don't know if NL=L or not yet. You showed that NL$\subseteq$ PSPACE, but it has nothing to do with L.
Snjór's user avatar
  • 23
2 votes
Accepted

Question on deduction that a certain problem requires exponential space

Here's one simple resolution. The statement referred to as "Fact 2" is a slightly weaker form of the standard Space Hierarchy Theorem. The standard version of the Space Hierarchy Theorem has the ...
William Hoza's user avatar
  • 1,743
2 votes
Accepted

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)$?

Interestingly, a pretty good answer to my question was already given in Wiedemann's seminal paper on solving sparse linear systems. I am actually quite familiar with the paper, but I had totally ...
Geoffroy Couteau's user avatar
1 vote

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

(Posting this as an answer because I am unable to comment.) There may be some confusion between models here. Width 5 read many branching programs capture $NC_1$, and width poly$(n)$ ordered branching ...
TedP's user avatar
  • 11
1 vote

Does LOGLOG = NLOGLOG?

If LOGLOG = NLOGLOG then LOG = NLOG. See more in: https://www.sciencedirect.com/science/article/pii/0304397590900086 and therefore, your question is still an unsolved problem.
Frank Vega's user avatar
1 vote

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

Assuming certain the hardness of certain computational problems, I think you should be able to do this in a more or less constant amount of space when you consider multisets. You can simply use a ...
Cryptonaut's user avatar
1 vote

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

Linear space lower bound follows from the communication problem of set disjointness. See http://www.math.ias.edu/~avi/PUBLICATIONS/HastadWi2007.pdf
Palash Dey's user avatar

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