Complete Problems for $DSPACE(\log(n)^k)$

Question

We know that the $polyL$-hierarchy doesn't have complete problems, as it would conflict with the space hierarchy theorem. But: Are there complete problems for each level of this hierarchy?

To be precise: Does the class $DSPACE(\log(n)^k)$ have complete problems under $L$-reductions for each $k > 0$?

Answer 1

A standard proof of the space hierarchy theorem is based on the space-efficient simulation of Turing machines. If I am not mistaken, this simulation implies that for every space-constructible function f: ℕ→ℕ, the following problem is in DSPACE(f(n)) (where n is the input length):

Given an encoding of a deterministic Turing machine M with a read-only input tape and a read-write work tape with a fixed work alphabet (such as {0, 1, blank}), a string x, and a tally string 1^t, decide whether M halts on input string x before using more than f(t) work space.

This problem is DSPACE(f(n))-hard under log-space many-one reducibility. Here is a proof in the case of f(n) = lg^kn. For each language L∈DSPACE(log^kn), there is a Turing machine M (of the form stated above) which accepts L in c lg^kn space for some c∈ℕ. Modify M to M′ so that when M rejects, M′ goes into an infinite loop instead. Then given an input string x, let t = |x|^c, and we generate the instance (M′, x, 1^t) of the problem above. (I think that the only slightly nontrivial part is that we cannot set t = |x|.)

Therefore this problem is DSPACE(f(n))-complete under log-space many-one reducibility.

Answer 2

Just an exetended comment.

In the paper "The Emptiness Problem for Intersections of regular Languages" it is showed that deciding the emptiness of the intersection of the languages recognized by $g(n)$ DFAs is complete for $NSPACE(g(n)\log{n})$; in particular the emptiness of the intersection of the languages recognized by $\log^{k-1}{n}$ DFAs is complete for $NSPACE(log^{k}{n})$, $k \geq 1$.

But it seems that the same result cannot be restricted to DPSACE if we consider the emptiness intersection of languages recognized by $g(n)$ Tally-DFAs (DFAs with only one symbol in the alphabet).

However $\emptyset = \bigcap^k DFA_{lin}$ is complete for $DSPACE(\log{n})$ for each $k$.