Buscando un buen problema dentro de SC pero no en los dos primeros niveles

El complejo zoológico no tiene mucho sobre . Estoy buscando un buen problema que se encuentra en los niveles superiores de la jerarquía, es decir, un problema en pero no se sabe que está en .$\mathsf{SC}$ † D T i m e S p a c e ( n O ( 1 ) , lg O ( 1 ) n) D T i m e S p a c e ( n O ( 1 ) , lg 2 n)$^\dagger$$\mathsf{DTimeSpace}(n^{O(1)},\lg^{O(1)} n)$$\mathsf{DTimeSpace}(n^{O(1)},\lg^2n)$

Como pregunta adicional, ¿hay alguna razón conocida por la cual encontrar ejemplos de problemas agradables en niveles superiores de jerarquías ( , , , , etc.) más difícil que los primeros niveles?N C S C P $\mathsf{AC}$$\mathsf{NC}$$\mathsf{SC}$$\mathsf{PH}$

N P N $\dagger$ aunque agradable no es un término matemático, creo que entendemos intuitivamente lo que significa, por ejemplo, aceptar un problema para NTM es un problema artificial que la gente no está interesada en él, aparte de estar completo para , mientras que el color del gráfico El problema era interesante antes de saber que estaba en / completo para y sigue siendo interesante, aparte de la clase de complejidad a la que pertenece.$\mathsf{NP}$$\mathsf{NP}$

No tengo una sugerencia para un problema natural en , pero sí tengo una sugerencia para su pregunta secundaria, de por qué encontrar tal El problema parece difícil. Creo que esto tiene algo que ver con la idea popular de que la gente solo puede comprender realmente (¿o tal vez solo le interesan las matemáticas? ¿O ambas?) Que son unas pocas alternancias cuantificadoras profundas. Por ejemplo, la definición de límite es de dos cuantificadores profundos (para todo épsilon existe un delta ...); la definición de " " es dos cuantificadores (existe una máquina tal que para todas las entradas ...), y la declaración " " es tres cuantificadores profundos.L ∈ N P P ≠ N $\mathsf{DTimeSpace}(n^{O(1)}, \log^4 n)$$L \in \mathsf{NP}$$\mathsf{P} \neq \mathsf{NP}$

Con respecto a , esto se ve confirmado por el hecho de que hay muchos problemas naturales que son -completos, muchos problemas naturales que son -completos, y solo unos pocos problemas naturales conocidos que son -completo (vea el compendio de Schaefer y Umans ). Los problemas más naturales que se sabe que están completos para niveles más altos de provienen de la lógica misma, lo cual es menos sorprendente ya que dentro de una lógica dada a menudo se tiene la noción de "N P Σ 2 P Σ 3 P P H$\mathsf{PH}$$\mathsf{NP}$$\mathsf{\Sigma_2 P}$$\mathsf{\Sigma_3 P}$$\mathsf{PH}$$k$-muchas alternancias cuantificadoras ", o al menos alguna forma natural de simularlo. Estas quizás caigan en la misma categoría que" aceptar problemas para MNA ", que ha declarado" no lo suficientemente bueno "para esta pregunta.

También vale la pena mencionar que sucede lo mismo en el mundo de la computabilidad, lo que tal vez sugiera que tiene que ver más con nuestra comprensión de los cuantificadores alternos y menos con la complejidad per se. Se sabe que muchos problemas naturales son -completos (equivalente al problema de detención), y se sabe que muchos problemas naturales están completos para el segundo y tercer nivel de la jerarquía aritmética. Pero a medida que avanza a niveles más altos de la jerarquía aritmética, se sabe que cada vez menos problemas naturales están completos para esos niveles. No estoy seguro de conocer un problema natural completo para , y nunca he oído hablar de un problema natural completo para (aunque tal vez lo haya). Σ 0 4 Σ 0 $\mathsf{\Sigma^0_1}$$\mathsf{\Sigma^0_4}$$\mathsf{\Sigma^0_5}$

Con respecto a los límites de espacio poliglogarítmico, creo que se aplica un razonamiento similar, pero aún más. Como , incluso los problemas que se encuentran en los "primeros pocos" niveles de la jerarquía " " son todos de hecho en (la jerarquía se colapsa), que está contenida en el espacio de registro cuadrado.N L N $\mathsf{NL} = \mathsf{coNL} \subseteq \mathsf{DSPACE}(\log^2 n)$$\mathsf{NL}$$\mathsf{NL}$