POLYLOGSPACE is the complexity class
$ \bigcup^\infty_{k=1} SPACE((logn)^k) $
(a) Show that, for any k, is $ A \in SPACE((logn)^k) $ and $ B \le _L A $, then $ B \in SPACE((logn)^k) $.
(b) Show that there are no POLYLOG-complete problems with respect to $ \le _L $ [Hint: use (a) and the Space Hierarchy Theorem]
NOTE:
"Space Hierarchy Theorem : Theorem For every constructible function $ f(n)\gt logn $,
$ SPACE(f(n)) \subsetneq SPACE(f(n)logf(n)) $.
Again, in Sipser’s book, a slightly stronger version of this theorem is given: for any constructible function f(n), there exists a language L decidable in space O(f(n)) but not in o(f(n)). As a consequence, we get
Theorem: $ L \subsetneq PSPACE $."
If someone could help with this question it would be greatly appreciated, as I'm not sure where to even begin.
(a) TL;DR, Reduce B to A in logarithmic space, then decide A in $()^$ space.
Step-by-step:
By def of $≤_{L}$,
For languages A and B, we write A $≤_{L}$ B to denote that there is a reduction f of A to B that is computable by a deterministic Turing machine using the same workspace.
$∈(()^)$. For any $a \in A, b \in B$, we could derive b = f(a) $\in (()^)$.
To sum up, we could compute $B∈(()^).$
Note: This showed that POLYLOGSPACE is closed under reductions. A complexity class C is said to be closed under reductions if whenever a language L ∈ C and L′ ≤ L, then L′ ∈ C.
(b)
By general Space Hierarchy Theorem from Wiki: For every constructible function $()$,
$(())⊊(o(()))$,
Take all integers $k > 0$,
$(()^)⊊(()^{+1}) \tag{1}, \forall k \in Z^{+}.$
Proof by contradiction, assume that POLYLOG had a complete problem,
Take arbitrary integer $k > 0$,
Suppose A is an element for the complete problem of $(()^)$.
Suppose B is an element of $(()^{+1})$.
Suppose B' is an element of $(()^{+1})$ \ $(()^)$.
By set difference,
$A⊄B' \tag{2}$
The assumption that POLYLOG is complete, A $≤_{L}$ B=, implies the following $()^$ space algorithm for B: Reduce B to A in logarithmic space, then decide A in $()^$ space. [Likewise in part (a)]
This implies that B' = B \ $(()^)$ is an element of $(()^)$, $A ⊊ B'$.
It violates the disjoint relationship $A⊄B'$, derived from the space hierarchy theorem! [see above (2)]
Hence, there are no POLYLOG-complete problems by contradiction.
Reference: polyLog (POLYLOG) wiki
Note: One proof that POLYLOG ≠ P is that P has a complete problem under logarithmic space many-one reductions but POLYLOG does not as shown here.