[Solved]: Complete Problems for $DSPACE(log(n)^k)$

ignougroup
Problem Detail: 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$?

Asked By : Mike B.

Answered By : Tsuyoshi Ito

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2088