Looking for a nice problem inside SC but not in the first two levels

Question

The complexity zoo doesn't have much about the $\mathsf{SC}$. I am looking for a nice$^\dagger$ problem that is in higher levels of the hierarchy, i.e. a problem in $\mathsf{DTimeSpace}(n^{O(1)},\lg^{O(1)} n)$ but not known to be in $\mathsf{DTimeSpace}(n^{O(1)},\lg^2n)$.

As a side question, is there any known reason why finding examples of nice problems in higher levels of hierarchies ($\mathsf{AC}$, $\mathsf{NC}$, $\mathsf{SC}$, $\mathsf{PH}$, etc.) is more difficult than the first levels?

$\dagger$ although nice is not a mathematical term I think we intuitively understand what it means, e.g. accepting problem for NTMs is an artificial problem that people are not interested in it aside from it being complete for $\mathsf{NP}$, while the graph coloring problem was interesting before being known to be in/complete for $\mathsf{NP}$ and is still interesting aside from the complexity class it belongs to.

Answer 1

I don't have a suggestion for a natural problem in $\mathsf{DTimeSpace}(n^{O(1)}, \log^4 n)$, but I do have a suggestion for your side question, of why finding such a problem seems difficult. I think this has something to do with the folk-idea that people can only really comprehend (or maybe are only interested in? or both?) math that is a few quantifier alternations deep. For example, the definition of limit is two quantifiers deep (for all epsilon there exists a delta...); the definition of "$L \in \mathsf{NP}$" is two quantifiers (there exists a machine such that for all inputs...), and the statement "$\mathsf{P} \neq \mathsf{NP}$" is three quantifiers deep.

With regards to $\mathsf{PH}$, this is somewhat borne out by the fact that there are lots of natural problems that are $\mathsf{NP}$-complete, many natural problems that are $\mathsf{\Sigma_2 P}$-complete, and only a few known natural problems that are $\mathsf{\Sigma_3 P}$-complete (see the compendium by Schaefer and Umans). The most natural problems known to be complete for higher levels of $\mathsf{PH}$ come from logic itself, which is less surprising since within a given logic one often has the notion of "$k$-many quantifier alternations," or at least some natural way to simulate it. These perhaps fall into the same category as "accepting problems for NTMs," which you've declared "not nice enough" for this question.

It might also be worth mentioning that the same thing happens in the world of computability, which maybe suggests that it has to do more with our understanding of alternating quantifiers and less with complexity per se. Lots of natural problems are known to be $\mathsf{\Sigma^0_1}$-complete (equivalent to the halting problem), and many natural problems are known to be complete for the second and third levels of the arithmetic hierarchy. But as you go to higher levels of the arithmetic hierarchy fewer and fewer natural problems are known to be complete for those levels. I'm not sure I know of a natural problem complete for $\mathsf{\Sigma^0_4}$, and I've never heard of a natural problem complete for $\mathsf{\Sigma^0_5}$ (though maybe there is).

With regards to polylogarithmic space bounds, I think a similar reasoning applies, but even more so. Since $\mathsf{NL} = \mathsf{coNL} \subseteq \mathsf{DSPACE}(\log^2 n)$, even problems that are in the "first few" levels of the "$\mathsf{NL}$ hierarchy" are all in fact in $\mathsf{NL}$ (the hierarchy collapses), which is contained in log-squared space.