25
It appears the problem is in L by [EJT10] and thus L-complete under $\text{NC}^1$ reducibility by [CM87]. See page 2 of [EJT10]:
Applying Theorem I.3 to the formula $\phi(X)$ expressing that $X$ is a
simple path from $s$ to $t$ shows that the problem $\{(G,s,t) \text{ }
| \text{ tw$(G) \leq k$, there is a path from $s$ to $t$ in $G$}\}$
lies in L
...
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 ...
14
The first half of this answer is nothing more than an efficient ($\log^4(n)$ to $\log^2(n)$) rephrasing of David's answer in complexity theoretic terms.
Context free languages live in the complexity class $LOGCFL.$ This class is equivalently characterized by log depth semi-unbounded circuits. These are polynomial sized circuits wherein OR gates have ...
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 ...
13
Any context free language can be described by a grammar in Chomsky Normal Form, and then recognized by a nondeterministic algorithm that uses $O(\log^2 n)$ bits of memory: just guess the top-level production ($O(1)$ bits) and the breakpoint in the input string between the two substrings matched by the two sides of the production ($O(\log n)$ bits), recurse ...
12
This answer expands my comment above.
You can do it with $O(\log e + \log \log b)$ space as follows:
1) First compute $b^e$ in Chinese remainder representation modulo sufficiently many primes.
2) Then use the Chiu-Davida-Litow algorithm to convert the Chinese remainder representation into binary representation. (Informatique Theoretique et Applications, ...
11
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 ...
9
Though not directly constructing a context sensitive grammar for SAT, the following paper might shed some light.
W. C. Rounds, Complexity of recognition in intermediate Level languages, Switching and Automata Theory, 1973, 145-158 http://dx.doi.org/10.1109/SWAT.1973.5
The paper by Rounds gives a one-way nondeterministic stack automaton (1-NSA) recognizing ...
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 ...
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
Deterministic CFL’s can be parsed in space $O(\log^2 n)$ and polynomial time (i.e., in $\mathrm{SC}^2$). This is an old result of Cook. It is an open problem whether nondeterministic CFL’s are also in SC (but this does not say anything about the existence of, say, linear space algorithms).
answered Oct 21 '11 at 17:42
Emil Jeřábek supports Monica
10.9k3 gold badges40 silver badges63 bronze badges
8
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
[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 (...
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
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 ...
5
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(...
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
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
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
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,\...
answered May 17 '18 at 20:58
Emil Jeřábek supports Monica
10.9k3 gold badges40 silver badges63 bronze badges
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
