Ищите хорошую проблему внутри СЦ, но не на первых двух уровнях

Сложность зоопарк не имеет много о $\mathsf{SC}$ . Я ищу хорошую † проблему, которая находится на более высоких уровнях иерархии, то есть проблему в D T i m e S p a c e ( n O ( 1 ) , lg O ( 1 ) n ), но о которой неизвестно в D Т я м ē S р с е ( п O ( 1 )$^\dagger$$\mathsf{DTimeSpace}(n^{O(1)},\lg^{O(1)} n)$ .$\mathsf{DTimeSpace}(n^{O(1)},\lg^2n)$

В качестве побочного вопроса, есть ли какая-либо известная причина, почему найти примеры хороших проблем на более высоких уровнях иерархий ( , N C , S C , P H и т. Д.) Сложнее, чем на первых уровнях?$\mathsf{AC}$$\mathsf{NC}$$\mathsf{SC}$$\mathsf{PH}$

$\dagger$ хотя хороший термин не является математическим, я думаю, что мы интуитивно понимаем, что он означает, например, принятие проблемы для NTM - это искусственная проблема, которая не интересует людей, если она не завершена для , в то время как проблема раскраски графов была интересна и раньше. известно, что он находится в / завершен для N P и по-прежнему интересен, кроме класса сложности, к которому он принадлежит.$\mathsf{NP}$$\mathsf{NP}$

У меня нет предложения для естественной проблемы в $\mathsf{DTimeSpace}(n^{O(1)}, \log^4 n)$ , но у меня есть предложение для вашего дополнительного вопроса, почему найти такой проблема кажется сложной. Я думаю, что это как-то связано с народной идеей, согласно которой люди могут действительно постигать (или, может быть, заинтересованы только в них? Или в обоих?) Математику, в которой есть несколько изменений квантификатора. Например, определение лимита составляет два квантификатора (для всех эпсилонов существует дельта ...); определение " $L \in \mathsf{NP}$«это два квантификатора (существует машина такая, что для всех входов ...), а утверждение« »имеет глубину три квантификатора.$\mathsf{P} \neq \mathsf{NP}$

Что касается , это в некоторой степени подтверждается тем фактом, что существует множество естественных задач, которые являются N P- полными, много естественных проблем, которые являются Σ 2 P -полными, и только несколько известных естественных проблем, которые являются Σ 3 P- полный (см. Сборник Шефера и Умана ). Наиболее естественные проблемы, которые, как известно, являются полными для более высоких уровней P H, возникают из самой логики, что не так удивительно, поскольку в рамках данной логики часто существует понятие « $\mathsf{PH}$$\mathsf{NP}$$\mathsf{\Sigma_2 P}$$\mathsf{\Sigma_3 P}$$\mathsf{PH}$$k$-много чередования квантификаторов "или, по крайней мере, каким-то естественным способом его моделирования. Возможно, они попадают в ту же категорию, что и" принятие проблем для NTM ", которые вы объявили" недостаточно хорошими "для этого вопроса.

Также стоит упомянуть, что то же самое происходит в мире вычислимости, что, возможно, говорит о том, что это связано с нашим пониманием чередующихся квантификаторов и меньше со сложностью как таковой. Много естественных проблем , как известно, -полным (эквивалент проблемы остановки), и многие природные проблемы , как известно, являются полными для второго и третьего уровней арифметической иерархии. Но по мере того, как вы переходите на более высокие уровни арифметической иерархии, для этих уровней становится все меньше и меньше естественных проблем. Я не уверен, что знаю о естественной задаче, полной для Σ 0 4 , и я никогда не слышал о естественной задаче, полной для Σ $\mathsf{\Sigma^0_1}$$\mathsf{\Sigma^0_4}$$\mathsf{\Sigma^0_5}$ (хотя, может быть, есть).

Что касается полилогарифмических границ пространства, я думаю, что аналогичные рассуждения применимы, но тем более. Так как , даже проблемы , которые находятся в «первых нескольких» уровней « N L иерархии» все в самом деле в N L (Коллапсы иерархии ), который содержится в лог-квадрате пространства.$\mathsf{NL} = \mathsf{coNL} \subseteq \mathsf{DSPACE}(\log^2 n)$$\mathsf{NL}$$\mathsf{NL}$