Szukasz ładnego problemu w SC, ale nie na pierwszych dwóch poziomach

Złożoność zoo nie ma wiele o . Szukam ładnego problemu z który jest na wyższych poziomach hierarchii, tj. Problemu w ale nie wiadomo, że jest w .$\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)$

Jako pytanie poboczne, czy istnieje jakiś znany powód, dla którego znajdowanie przykładów dobrych problemów na wyższych poziomach hierarchii ( , , , itp.) Jest trudniejsze niż pierwsze poziomy?N C S C P $\mathsf{AC}$$\mathsf{NC}$$\mathsf{SC}$$\mathsf{PH}$

N P N $\dagger$ chociaż miły nie jest terminem matematycznym, myślę, że intuicyjnie rozumiemy, co to znaczy, np. akceptacja problemu dla NTM jest sztucznym problemem, że ludzie nie są zainteresowani, poza tym, że jest kompletny dla , podczas gdy kolorowanie wykresu problem był interesujący, zanim uznano, że jest w / complete for i nadal jest interesujący oprócz klasy złożoności, do której należy.$\mathsf{NP}$$\mathsf{NP}$

Nie mam propozycji naturalnego problemu w , ale mam sugestię na pytanie poboczne, dlaczego warto znaleźć taki problem wydaje się trudny. Myślę, że ma to coś wspólnego z ludową ideą, że ludzie mogą naprawdę zrozumieć (a może są zainteresowani tylko? Lub obiema?) Matematyką o głębokości kilku alternatywnych kwantyfikatorów. Na przykład definicja limitu to dwa kwantyfikatory głębokie (dla wszystkich epsilonów istnieje delta ...); definicja „ L ∈ N $\mathsf{DTimeSpace}(n^{O(1)}, \log^4 n)$$L \in \mathsf{NP}$”to dwa kwantyfikatory (istnieje maszyna taka, że ​​dla wszystkich wejść ...), a wyrażenie„ ”ma głębokość trzech kwantyfikatorów.$\mathsf{P} \neq \mathsf{NP}$

W odniesieniu do , to jest w pewnym stopniu potwierdza fakt, że istnieje wiele problemów, które są naturalnymi N P -Complete, wiele problemów, które są naturalne Σ 2 P -Complete, a tylko kilka znanych naturalnych problemów, które są Σ 3 P -kompletny (patrz kompendium Schaefera i Umansa ). Najbardziej naturalnym problemy znane jako kompletne do wyższych poziomów P H pochodzą z samej logiki, która jest mniej zaskakujące, ponieważ w ciągu dana jedna logika często pojęcie " $\mathsf{PH}$$\mathsf{NP}$$\mathsf{\Sigma_2 P}$$\mathsf{\Sigma_3 P}$$\mathsf{PH}$$k$- wiele alternatywnych kwantyfikatorów ”lub przynajmniej jakiś naturalny sposób ich symulacji. Być może należą one do tej samej kategorii co„ akceptowanie problemów dla NTM ”, które zadeklarowaliście jako„ niewystarczająco miłe ”na to pytanie.

Warto również wspomnieć, że to samo dzieje się w świecie obliczalności, co może sugerować, że ma to więcej wspólnego z naszym rozumieniem przemiennych kwantyfikatorów, a mniej ze złożonością per se. Wiadomo, że wiele naturalnych problemów jest -kompletnych (odpowiednik problemu zatrzymania), a wiele naturalnych problemów jest znanych dla drugiego i trzeciego poziomu hierarchii arytmetycznej. Ale kiedy przechodzisz na wyższe poziomy hierarchii arytmetycznej, wiadomo, że coraz mniej naturalnych problemów jest ukończonych dla tych poziomów. Nie jestem pewien, czy wiem o naturalnym problemie kompletnym dla Σ 0 4 i nigdy nie słyszałem o naturalnym problemie kompletnym dla Σ 0 $\mathsf{\Sigma^0_1}$$\mathsf{\Sigma^0_4}$$\mathsf{\Sigma^0_5}$ (choć może jest).

Jeśli chodzi o granice przestrzeni polilogarytmicznej, myślę, że stosuje się podobne rozumowanie, ale jeszcze bardziej. Ponieważ , nawet problemy, które znajdują się na „pierwszych kilku poziomach” „ N L hierarchii”, w rzeczywistości są w N L (hierarchia się załamuje ), który jest zawarty w przestrzeni z logarytmem do kwadratu.$\mathsf{NL} = \mathsf{coNL} \subseteq \mathsf{DSPACE}(\log^2 n)$$\mathsf{NL}$$\mathsf{NL}$