25

You can use the same argument used to prove the $\Omega(n^2)$ time bound on single tape. Suppose that you have a TM with $S(n)$ space that recognize palindromes $\{x\,0^{\frac{n}{3}} x^R \mid |x|=n/3 \}$ (where $x^R$ is the reverse of $x$) in time $T(n)$. When the (input) head crosses the middle $0^{n/3}$ it can carry only $S(n)$ bits of information. So it ...


22

Using crossing sequences or communication complexity it is simple to derive the tradeoff $T(n)S(n) = \Omega(n^2)$ for a sequential Turing machine using time $O(T(n))$ and space $O(S(n))$. This result was first obtained by Alan Cobham using crossing sequences in the paper The recognition problem for the set of perfect squares which appeared at SWAT (later ...


16

Just to get things going, rather than trying to close out this problem: there is an obvious nondeterministic algorithm using logarithmically many bits of space (search for a single path through the dynamic programming matrix) so by Savitch's theorem there is a deterministic algorithm with space $O(\log^2 n)$. Its time must be of the form $n^{O(\log n)}$, ...


15

There is no need for the tradeoff that Yuval suggests. The entire optimal editing sequence can be computed in $O(nm)$ time and $O(n+m)$ space, using a mixture of dynamic programming and divide-and-conquer first described by Dan Hirschberg. (A linear space algorithm for computing maximal common subsequences. Commun. ACM 18(6):341–343, 1975.) Intuitively, ...


10

You can get the situation you describe by choosing weird functions $f(n)$ and $g(n)$. For example, let $g(n) = n^3$ and $$f(n) = \begin{cases} n & \text{if $n$ is odd}, \\\ 2^{n^5} & \text{if $n$ is even}. \end{cases} $$ Then choose $L_1$ and $L_2$ as follows: $L_1$ is a language containing only strings of even length which can be decided in ...


9

A full proof (based on superconcentrators) can be found in chapter 24 "The pebble game" of the book Uwe Schöning and Randall Pruim: Gems of Theoretical Computer Science Springer, 1998 ISBN 978-3-642-64352-1 https://link.springer.com/book/10.1007%2F978-3-642-60322-8


7

This would imply that L⊊NP since L⊆TISP(poly(n),n^k) k∈N


6

Compact reachability oracles exist for planar graphs, Mikkel Thorup: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6): 993-1024 (2004) but are "hard" for general graphs (even sparse graphs) Mihai Patrascu: Unifying the Landscape of Cell-Probe Lower Bounds. SIAM J. Comput. 40(3): 827-847 (2011) Nevertheless, ...


6

Not sure whether I am missing something, but... The Omega(n/log n) lower bound is from: [PTC77] Wolfgang J. Paul, Robert Endre Tarjan, and James R. Celoni. Space bounds for a game on graphs. Mathematical Systems Theory, 10:239–251, 1977. There is a strengthening of this to a non-deterministic version of the pebble game (so-called black-white pebbling) in: ...


5

Did you try searching Google scholar for "induced cycle basis"? There is not much, but the following reference seems to be relevant. It characterizes the graphs for which the set of all induced cycles forms a cycle basis, which I think is more restrictive than your question (you are allowing a proper subset of these cycles in your basis). McKee, Terry A. (...


4

I'll answer your question partially: there seem to be some reasons why such a construction may be hard to obtain. Suppose that given any n-node m-edge directed graph you could preprocess it in T(m,n) time so that reachability queries can be answered in q(m,n) time. Then, for instance, you could find a triangle in an n-node m-edge graph in $T(O(m),O(n))+n q(...


3

In addition to the other answers, it's worth noting that if randomization is allowed, palindromes can be recognized with O(1) space and O(n) time by hashing the left side of the string, hashing the transpose of the right side of the string, and checking if the hashes are equal. It shouldn't be hard to do this on a Turing machine.


3

The algorithm you describe that runs in space $O(n_1 + n_2)$ actually recovers the final edit, and the state just before the final edit. So if you run this algorithm $O(n_1 + n_2)$ times, you can recover the entire edit sequence, at the expense of increasing the runtime. In general, there is a time-space trade-off which is controlled by the number of rows ...


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

Here is a construction with $3N + O(\lg N)$ adder computations/uncomputations and $2 \lg(N)$ ancilla usage. Divide the input into $N/\lg N$ groups of size $\lg N$. Allocate a result register of size $\lg N$. For each group $g$: Use the naive strategy to compute $g$'s weight using $\lg N$ adder computations and space. Add the weight into the result register ...


2

A sketch data structure is an approximation of a set of elements. Sketches vary in what they store -- some store just hashes, some store elements from the set (a sample), and some store floating-point numbers. This solution uses the sketch data structure from "A Minimal Variance Estimator for the Cardinality of Big Data Set Intersection", by Cohen et al. It ...


1

In some sense yes, specifically as of right now we have that: $\textbf{DTIME}(S(n)) \subseteq \textbf{SPACE}(S(n)) \subseteq \textbf{NSPACE}(S(n)) \subseteq \textbf{DTIME}(2^{O(S(n))})$ And also we know that $\textbf{PSPACE} \subsetneq \textbf{EXPSPACE}$ So that also implies $\textbf{P} \subsetneq \textbf{EXPSPACE}$. Though we don't know what the specific ...


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