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$?


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 1t, 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) = lgkn. For each language L∈DSPACE(logkn), there is a Turing machine M (of the form stated above) which accepts L in c lgkn 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, 1t) 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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.