<p>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.</p>

<p>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 <a href="http://ovid.cs.depaul.edu/documents/phcom.pdf">compendium by Schaefer and Umans</a>). 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.</p>

<p>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).</p>

<p>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.</p>

CC BY-SA 3.0
2012-05-08T21:37:40.763Z
This is a very interesting answer.
Suresh Venkat
CC BY-SA 3.0
2012-05-11T03:18:09.713Z
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.
Kaveh
CC BY-SA 3.0
2012-05-08T19:51:40.473Z
2012-05-08T19:51:40.473Z
Joshua Grochow
<p>The <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aS#sc">complexity zoo</a> doesn't have much about the <a href="http://en.wikipedia.org/wiki/SC_%28complexity%29">$\mathsf{SC}$</a>. 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)$.</p>

<p>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? </p>

<p>$\dagger$ although <em>nice</em> 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.</p>

CC BY-SA 3.0
2012-04-28T22:45:47.413Z
(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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-04-28T22:46:48.303Z
(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”?
Tsuyoshi Ito
CC BY-SA 3.0
2012-04-29T01:32:40.233Z
@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)$.
Kaveh
CC BY-SA 3.0
2012-04-29T11:06:07.073Z
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).
Tsuyoshi Ito
CC BY-SA 3.0
2012-04-29T14:26:55.167Z
@Tsuyoshi, I am not sure what you mean by $\lg^4$ being simpler than $\lg^2$. The question also applies to $\mathsf{P}$.
Kaveh
CC BY-SA 3.0
2012-04-29T14:27:25.400Z
Let me speculate about something deeper that I think might be at play: the nice problems can also be stated in a particular form and the problems in that form fall in a small number of classes, something like the Dichotomy theorems for CSPs.
Kaveh
CC BY-SA 3.0
2012-04-29T15:05:11.763Z
“I am not sure what you mean by lg^4 being simpler than lg^2.”  I did not say a ridiculous thing like that.
Tsuyoshi Ito
CC BY-SA 3.0
2012-04-29T17:22:38.863Z
@Tsuyoshi, I think it is clear that was a typo, what I meant was: I am not sure what you mean by $\lg^2$ being simpler than $\lg^4$.
Kaveh
<cc.complexity-theory><complexity-classes>
Looking for a nice problem inside SC but not in the first two levels
Kaveh
# Looking for a nice problem inside SC but not in the first two levels

(Asked by: username_0 on 2012-04-28)

The [complexity zoo](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aS#sc) doesn't have much about the [$\mathsf{SC}$](http://en.wikipedia.org/wiki/SC_%28complexity%29). 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.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: (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.  
> **username_1**: (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”?  
> **username_0**: @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)$.  
> **username_1**: 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).  
> **username_0**: @Tsuyoshi, I am not sure what you mean by $\lg^4$ being simpler than $\lg^2$. The question also applies to $\mathsf{P}$.  
> **username_0**: Let me speculate about something deeper that I think might be at play: the nice problems can also be stated in a particular form and the problems in that form fall in a small number of classes, something like the Dichotomy theorems for CSPs.  
> **username_1**: “I am not sure what you mean by lg^4 being simpler than lg^2.”  I did not say a ridiculous thing like that.  
> **username_0**: @Tsuyoshi, I think it is clear that was a typo, what I meant was: I am not sure what you mean by $\lg^2$ being simpler than $\lg^4$.  

---

## 1 answers

### Answer by username_2 on 2012-05-08. Score: 12 | Accepted answer

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](http://ovid.cs.depaul.edu/documents/phcom.pdf)). 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.

> **Comments:**
> **username_3**: This is a very interesting answer.  
> **username_0**: 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.  

---

