# Tag Info

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 ...

19

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 ...

19

Most computations in algebraic geometry / commutative algebra. Most involve computing Grobner bases, which are EXPSPACE-hard in general. There are some parameter regimes where this improves and thus some computations can reasonably be done in practice (e.g. using Macaulay2 or SINGULAR), but very often it quickly eats up all the space and crashes. I think ...

15

This situation comes up frequently in crypto, where you want to generate hard problem instances along with their solutions. For example, there is the work of Eric Bach (and later, Adam Kalai) on efficiently generating random integers with their prime factorizations. One of many interesting observations of Impagliazzo and Wigderson (Randomness vs time: ...

11

$\mathbf{UL}$ is contained in $\mathbf{NL}$, which is contained in $\mathbf{DSPACE}(\log^2 n)$ by Savitch's theorem, which is strictly contained in $\mathbf{PSPACE}$ by the space hierarchy theorem, so $\mathbf{UL}$ is strictly contained in $\mathbf{PSPACE}$. It would be surprising if e.g. $\mathbf{UL} = \mathbf{DSPACE}(\log^2 n)$, but I don't think it's ...

10

Indeed, using the resultss in Elberfeld-Jakoby-Tantau-2010 one can show that SAT can be decided in logspace on formulas whose incidence graph has bounded treewidth. Here is a sketch of how the main steps of the proof of this claim go. The notions of tree-decomposition and treewidth can be generalized to arbitrary relational structures. See for instance ...

10

Here is an algorithm that uses $2k^2 + O(\log n)$ space. This is just the observation that the well known "Buss kernel" for Vertex Cover can be computed in log-space: Say that a vertex has big degree if it has degree at least $k+1$. All vertices of big degree must be in every vertex cover of size at most $k$. If $v$ does not have big degree it has small ...

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 ...

8

My go-to answer for this (the one I use in undergraduate algorithms classes) is the Bellman–Held–Karp dynamic programming algorithm for the traveling salesperson problem (https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm). It's not the choice in practice for this problem (instead, branch-and-cut methods like in CONCORDE are faster) but it has the ...

8

In knowledge compilation, the task is to compile some set $A\subseteq \{0,1\}^n$ into a format such that various queries can then be answered in polynomial time. For example, you can "compile" the set of satisfying assignments to a CNF formula $\psi$ into a Binary Decision Diagram (a kind of directed acyclic labelled graph). Once this is (expensive)...

7

Yes. I think the main reference is Turing Machines with Sublogarithmic Space by Szepietowski (1994). (Link to books.google)

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

Dynamic programming is probably a general case of this but one specific, practically relevant and illustrative example is (global) pairwise sequence alignment using the Needleman–Wunsch algorithm, which has both time and space complexity $\mathcal O(nm)$. When applied to mammalian whole-genome alignments, this would naïvely require in the order of exabytes ...

6

Define the language $BACKPOINTER$ to have words of length $n+t\log n$, divided to $1+t$ parts, one of length $n$ and the rest of length $\log n$, by commas such that $BACKPOINTER=\{(x,p_1,\ldots,p_t)\mid x_{p_i}=1 \forall i\}$. It should follow from some standard one-way communication complexity bound that $BACKPOINTER$ needs at least $t$ bits of memory ...

6

If I got this right, $\Pi_2L$ as defined above is equal to co-NP. The co-NP-complete DNF tautology sits in $\Pi_2L$: Use z for the assignment and y to choose which clause to check. To show $\Pi_2L$ in co-NP, universally guess z and the rest can be computed in P.

5

In general, CTL model checking is P-complete. Since we think that $L\neq P$ (and moreover $NL\neq P$), it is unlikely that an algorithm with logarithmic space exists. It is also unlikely that a sub-polynomial space algorithm exists, for similar reasons of common belief. I don't know of exact space-optimizations for the problem, but in general - yes, you ...

5

I don't know if the space complexity of this problem is limiting in practice (I have not personally run experiments to verify this, moreover I don't know anyone who needs to solve exact SVP in practice --- approximating it to some polynomial approx factor is already sufficient to break cryptography), but algorithms solving the Shortest Vector Problem in $n$-...

5

One example is multicommodity flow problems via Simplex method. In these problems we have a graph $G=(V,E)$ with $n$ nodes and $m$ edges and $K$ commodities. The number of variables is $Km$ (one per commodity and edge pair) and the number of constraints is roughly $m$. Now if you try to run the flow problem via simplex based algorithms then the incidence ...

5

No, this is impossible for your parameters. With $s$ bits of space, you can only visit at most $2^s$ vertices of the graph. Now set $s = O((\log k)^d)$ and $k=(\log n)^2$ and it is clear that you cannot visit all of the graph, as $2^s = o(n)$. Thus for any algorithm that uses only $O((\log k)^d)$ bits of space, there exist graphs where you fail to detect ...

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

First, I don't think the Arthur-Merlin protocol has to enter the model -- it sounds from the motivation like you just want to produce problem instances quickly so that any algorithm for solving them is slow. In other words, if we could prove that Arthur can produce a hard problem, then there seems to be no need for Merlin to verify that the problem produced ...

4

The main difference between time and space is that you can reuse space that is not needed anymore. If you return from the recursive call that evaluates $A$, you can reuse the space used by this computation to compute the value of $B$. Because of this you only need to store one branch of the decision tree of the original QBF formula in memory, which gives ...

4

With this question we actually have to worry about $O(1)$ factors, because as you point out time can't be little o of space, but it can be much less demanding as a fraction of our hardware's abilities. A historical example, in which many algorithms could be discussed to make the point, would be old-school video games. I won't go into much detail here, but ...

3

Yes, sliding blocks, Rush Hour, and many other puzzles with reversible moves are (deterministic) linear space complete. By contrast, many puzzles with irreversible moves, including Sokoban, are complete for nondeterministic linear space. Sliding blocks is in linear space because the state has $O(n)$ bits and the moves are reversible (and undirected graph ...

3

Yes. It is essentially same as the Clique problem. Imagine a clique containing $n$ nodes. Your problem is then asking for a Clique containing $n-1$ nodes, such that all of them are adjacent to vertex $v$. $v$ is connected to all vertices in the graph. The problem is still NPComplete.

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 If I understand your question correctly, as far as I understand this is computational-model dependent. An excellent lecture on the subject by Prof. Ryan O'Donnell can be found here: https://www.youtube.com/watch?v=_nCBH_lVjGU 3 I think we have a reference here to Joel Hamkin's model of infinite time computation, not just some made up idea of infinite time machines. In that model time is measured by ordinal numbers. The machine has access to an infinite tape. After$\omega\$ steps, every cell of the tape has been potentially written to, and we can't throw away any cell because its ...

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.

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