patternMinor
Complete Problems for $DSPACE(\log(n)^k)$
Viewed 0 times
dspacelogcompleteforproblems
Problem
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$?
To be precise: Does the class $DSPACE(\log(n)^k)$ have complete problems under $L$-reductions for each $k > 0$?
Solution
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.
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.
Context
StackExchange Computer Science Q#2088, answer score: 7
Revisions (0)
No revisions yet.