Procurando um bom problema dentro do SC, mas não nos dois primeiros níveis

O zoológico de complexidade não tem muito a ver com o . Estou procurando um bom problema de que esteja nos níveis mais altos da hierarquia, isto é, um problema no mas não se sabe que está em .$\mathsf{SC}$$^\dagger$$\mathsf{DTimeSpace}(n^{O(1)},\lg^{O(1)} n)$$\mathsf{DTimeSpace}(n^{O(1)},\lg^2n)$

Como uma questão paralela, existe algum motivo conhecido para encontrar exemplos de bons problemas em níveis mais altos de hierarquias ( , , , , etc.) mais difícil do que os primeiros níveis?$\mathsf{AC}$$\mathsf{NC}$$\mathsf{SC}$$\mathsf{PH}$

$\dagger$ embora agradável não seja um termo matemático, acho que compreendemos intuitivamente o que significa, por exemplo, aceitar problema para MNTs é um problema artificial que as pessoas não estão interessadas nele, além de estarem completas para , enquanto o gráfico está colorindo O problema era interessante antes de ser conhecido por estar em / completo para e ainda é interessante além da classe de complexidade à qual pertence.$\mathsf{NP}$$\mathsf{NP}$

Eu não tenho uma sugestão para um problema natural em , mas eu tenho uma sugestão para sua pergunta paralela, de por que encontrar tal problema parece difícil. Eu acho que isso tem algo a ver com a ideia popular de que as pessoas só podem realmente compreender (ou talvez só estejam interessadas em? Ou em ambas?) Matemática com algumas alternâncias quantificadoras profundas. Por exemplo, a definição de limite é de dois quantificadores de profundidade (para todo epsilon existe um delta ...); a definição de " L ∈ N $\mathsf{DTimeSpace}(n^{O(1)}, \log^4 n)$$L \in \mathsf{NP}$"é dois quantificadores (existe uma máquina tal que para todas as entradas ...), e a instrução" "tem três quantificadores de profundidade.$\mathsf{P} \neq \mathsf{NP}$

Com relação a , este é um pouco corroborada pelo facto de que existem muitos problemas naturais que são N P -completo, muitos problemas que são naturais Σ 2 P -completo, e apenas alguns problemas naturais conhecidos, que são Σ 3 P -complete (veja o compêndio de Schaefer e Umans ). A maioria dos problemas naturais conhecidos para ser completa para níveis mais elevados de P H vir da própria lógica, que é menos surpreendente, uma vez dentro de um dado uma lógica muitas vezes tem a noção de " $\mathsf{PH}$$\mathsf{NP}$$\mathsf{\Sigma_2 P}$$\mathsf{\Sigma_3 P}$$\mathsf{PH}$$k$- muitas alternativas de quantificador ", ou pelo menos uma maneira natural de simulá-lo. Elas talvez se enquadram na mesma categoria de" aceitação de problemas para NTMs ", que você declarou" não é agradável o suficiente "para esta pergunta.

Também vale a pena mencionar que o mesmo acontece no mundo da computabilidade, o que talvez sugere que isso tenha mais a ver com o entendimento de quantificadores alternados e menos com a complexidade em si. Sabe-se que muitos problemas naturais são completos ou (equivalentes ao problema de parada) e muitos problemas naturais são completos para o segundo e o terceiro níveis da hierarquia aritmética. Mas à medida que você avança para níveis mais altos da hierarquia aritmética, sabe-se que cada vez menos problemas naturais estão completos para esses níveis. Não tenho certeza se conheço um problema natural completo para Σ 0 4 e nunca ouvi falar de um problema natural completo para Σ 0 $\mathsf{\Sigma^0_1}$$\mathsf{\Sigma^0_4}$$\mathsf{\Sigma^0_5}$ (embora talvez exista).

Com relação aos limites do espaço polilogarítmico, acho que um raciocínio semelhante se aplica, mas ainda mais. Como , mesmo problemas que estão nos "primeiros poucos" níveis da " hierarquia N L " são todos de fato em N L (a hierarquia entra em colapso ), que está contido no espaço do log-quadrado.$\mathsf{NL} = \mathsf{coNL} \subseteq \mathsf{DSPACE}(\log^2 n)$$\mathsf{NL}$$\mathsf{NL}$