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}$ $^\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? $\mathsf{AC}$ $\mathsf{NC}$ $\mathsf{SC}$ $\mathsf{PH}$

$\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}$

cc.complexity-theory complexity-classes

— Kaveh
źródło

(1) „zaakceptowanie problemu dla NTM nie jest sztucznym problemem, że ludzie nie są nim zainteresowani, poza tym, że jest kompletny dla NP”: wydaje się, że masz tu nadmierne „nie”.

— Tsuyoshi Ito

(2) „Jako pytanie poboczne, czy jest jakiś znany powód, dla którego znalezienie przykładów miłych problemów na wyższych poziomach hierarchii (AC, NC, SC, PH itp.) Jest trudniejsze niż na pierwszych poziomach?” Czy potrzebujesz głębszy powód niż „niższe poziomy są prostsze i dlatego jest w nich wiele dobrych przykładów”?

— Tsuyoshi Ito

@Tsuyoshi, dzięki, usunąłem dodatkowe nie. Około 2, tak, potrzebuję głębszego powodu, aby ładne problemy spadały na niskie poziomy hierarchii. Nie widzę dużej różnicy między

i powiedzieć

D T i m e S p a c e (n^{O (1)}, \lg^{2} n)

$\mathsf{DTimeSpace}(n^{O(1)},\lg^2 n)$

D T i m e S p a c e (n^{O (1)}, \lg^{4} n)

$\mathsf{DTimeSpace}(n^{O(1)},\lg^4 n)$

— Kaveh

Oczywiście definicja jest taka sama. Różnica polega na tym, że log ^ 2 jest prostszy niż log ^ 4. Ten sam argument dotyczy pytania, dlaczego istnieje o wiele więcej algorytmów działających w czasie O (n ^ 2) niż tych, które działają w czasie O (n ^ 4).

— Tsuyoshi Ito

@Tsuyoshi, nie jestem pewien, co masz na myśli mówiąc, że

jest prostsze niż

. Pytanie dotyczy również

\lg^{4}

$\lg^4$

\lg^{2}

$\lg^2$

P

$\mathsf{P}$

— Kaveh

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 „ $\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 -Complete, wiele problemów, które są naturalne -Complete, a tylko kilka znanych naturalnych problemów, które są -kompletny (patrz kompendium Schaefera i Umansa ). Najbardziej naturalnym problemy znane jako kompletne do wyższych poziomów 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 i nigdy nie słyszałem o naturalnym problemie kompletnym dla $\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” „ hierarchii”, w rzeczywistości są w (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}$

— Joshua Grochow
źródło

To bardzo interesująca odpowiedź.

— Suresh Venkat

Dzięki, Joshua, to naprawdę miłe spostrzeżenie. Sugeruje to z perspektywy epistemologicznej: to, co dla ludzi wygląda naturalnie, ma ograniczoną złożoność kwantyfikatora.

— Kaveh