18
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (1) “accepting problem for NTMs is not an artificial problem that people are not interested in it aside from it being complete for NP”: seems you have an excessive “not” here. $\endgroup$ – Tsuyoshi Ito Apr 28 '12 at 22:45
  • $\begingroup$ (2) “As a side question, is there any known reason why finding examples of nice problems in higher levels of hierarchies (AC, NC, SC, PH, etc.) is more difficult than the first levels?” Do you need a deeper reason than “Lower levels are simpler and therefore there are many nice examples in them”? $\endgroup$ – Tsuyoshi Ito Apr 28 '12 at 22:46
  • $\begingroup$ @Tsuyoshi, thanks, I removed the extra not. About 2, yes, I need a deeper reason for nice problems falling in the low levels of hierarchies. I don't see a big definitional difference between $\mathsf{DTimeSpace}(n^{O(1)},\lg^2 n)$ and say $\mathsf{DTimeSpace}(n^{O(1)},\lg^4 n)$. $\endgroup$ – Kaveh Apr 29 '12 at 1:32
  • 1
    $\begingroup$ Of course the definition is the same. The difference is that log^2 is simpler than log^4. The same argument applies to asking why there are many more algorithms which run in time O(n^2) than those which run in time O(n^4). $\endgroup$ – Tsuyoshi Ito Apr 29 '12 at 11:06
  • $\begingroup$ @Tsuyoshi, I am not sure what you mean by $\lg^4$ being simpler than $\lg^2$. The question also applies to $\mathsf{P}$. $\endgroup$ – Kaveh Apr 29 '12 at 14:26
12
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ This is a very interesting answer. $\endgroup$ – Suresh Venkat May 8 '12 at 21:37
  • 1
    $\begingroup$ Thanks Joshua, this is indeed a nice observation. It kind of suggests an epistemological perspective: what looks natural to humans are of limited quantifier complexity. $\endgroup$ – Kaveh May 11 '12 at 3:18

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.