18
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 if $G_k (n)$ is the number of distinct languages accepted by NFA's with $n$ states over a $k$-letter alphabet, and $g_k (n)$ is similarly the number of distinct ...
13
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$ in an outdegree one graph $G$, that is promised to be a path) is $\mathsf{L}$-hard under quantifier free projections.
The problem $\mathbf{ORD}$ can be seen ...
12
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 decreased to $O(S)$.
In particular, in the setting you describe, we have $S = O(\log n)$, so the number of random bits can be reduced to $O(\log n)$. Then, we can ...
11
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 logspace" and you will find plenty of references. (Typically, past work treats it as a reducibility concept.) The papers that those papers reference should cover ...
9
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: you have two sorted lists of length $m$, and you would like to create a sorted list of the pairwise sums of the numbers in the lists. You would like to do this ...
9
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(DCFL) vs Log(CFL). Have a great day!
http://link.springer.com/chapter/10.1007%2F978-3-642-14031-0_35#page-1
http://link.springer.com/chapter/10.1007/3-540-...
8
I have found an answer to my own question. The result was given in Section 5 of Karpinski and Verbeek, 1987.
For any input of length $ n $, a PTM can construct $ \Theta(\log \log n) $ space with high probability (Section 4). (With a very small probability, the machine can also construct logarithmic space, and this might be seen as a "drawback" of the ...
8
[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 same lower bound for inputs of sufficiently small bit-size it would imply $\mathsf{P} \neq \mathsf{NC}$ (and hence $\mathsf{P} \neq \mathsf{L}$). This is, at a ...
7
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 Wehar
We carefully reexamine a construction of Karakostas, Lipton, and Viglas (2003) to show that the intersection
non-emptiness problem for DFA's (deterministic ...
7
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 regular domains.
7
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 program computing $f$. By an argument analogous to this hierarchy argument for circuit size, one can show that there are constants $\epsilon, c$ so for every ...
7
$\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 branching programs can simulate each other with polynomial blow-up, so polynomial size skew circuits and branching programs compute the same class of functions, ...
6
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/\log n))$.
However, under plausible computational complexity conjectures, there is a proper hierarchy. For example, if for every $ε>0$, CIRCUIT-SAT ∉ i.o.-$O(...
6
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. The problem of stating them was raised in 1978 by
Sakoda and Sipser [32], with the conjecture that they are not
polynomial. In spite of all attempts to ...
5
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 [insert, delete, lookup] operations in the worst case with high probability" while using $B + o(B)$ bits, where $B$ is the lower bound you mention.
If you need ...
5
I think Amnon Ta-Shma's new result is a good answer to my own question.
Amnon Ta-Shma: Inverting well conditioned matrices in quantum logspace. STOC 2013: 881-890. (copy from author's website)
... We show that the inverse of a well conditioned matrix can be approximated in quantum logspace with intermediate measurements. This should be compared with the ...
4
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 is coNP-complete even if there are only two layers.
In general if a variable is read more than one time it is NP-complete if I remember correctly.
4
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$ and $\sum y_i = M-r$. There are exactly $\binom{M-1}{r-1}$ such ways (see e.g. here). Now, if there are only $k$ possible values for a variable, then $\lceil \log ...
4
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 $x$; that is, the number of $x'$ s.t. $p(x') > p(x)$: just go over all $x'\in \{0,1\}^n$ and count the number of $x'$ s.t. $p(x') > p(x)$. Note that $r(x)$ ...
4
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 one recognized by a deterministic linear bounded automaton
(DLBA). We note $n$ the size of the input string $w$. We restrict the
problem, w.l.o.g, to DLBAs that ...
4
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 check-outs in the other, but that makes little difference) in my paper
Space-efficient straggler identification in round-trip data streams via Newton's ...
3
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, $k_1$ and $k_2$ be the number of unique elements in the sets, and $n_1$ and $n_2$ be the sum of the lengths of all elements in the sets.
General Solutions
...
3
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 decoded in logarithmic space.)
Let $k$ be a sufficiently large constant, and consider the following encoding scheme for $X\subseteq\{0,\dots,n-1\}$. Split $\{0,\...
3
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 all large enough $n$.
By the standard simulation, a TM with $q$ states that uses at most $s$ bits of space can be simulated by a TM that has at most $qns2^s = 2^...
3
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 into it):
Suppose that over alphabet $\Sigma = \{0,1\}$ you encode a MPA using a list of transitions:
$s,a,p \rightarrow s',p',L|R;...\#$
where $s$ is the ...
3
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 and $\log(N(|k|+2))+|k|+2$ bits to store a counter; if the counter cycles, the simulated machine will never halt. This is linear in |k| (ignoring the O(N \log ...
3
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 machine could enumerate all these states, and check whether one of them is accepting.
But this is not enough. To faithfully simulate the NL machine, the ...
2
Yes, this can be done through bucketing. The representation in Briggs and Torczon can be used to store not just bits, but values associated with any set bits, by storing them next to the values in the dense array. For $k$-bit values, this leads to a total storage cost of $(2n+1)\lceil \lg n \rceil + kn$.
Now pick $k=\lceil \lg n \rceil$. Each $k$-bit value ...
2
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))})$.
This matches the known inclusions $\text{DSPACE}(\log n) = \text{L} \subseteq \text{L}/poly = \text{BP}(poly)$; if a better bound were known then I would expect ...
2
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 read-only input tape and one work tape, both over binary alphabet $\Sigma = \{0,1\}$, for every decider with $c$ states on an input of size $n$ we have that :
$$...
Only top voted, non community-wiki answers of a minimum length are eligible
