Dlaczego traktujemy log-space jako model wydajnego obliczania (zamiast polilog-space)?

To może być pytanie subiektywne, a nie konkretne, ale tak czy inaczej.

W teorii złożoności badamy pojęcie wydajnych obliczeń. Istnieją klasy takie jak oznacza czas wielomianowy , a L oznacza miejsce na log . Oba są uważane za reprezentowane jako rodzaj „wydajności” i dość dobrze wychwytują trudności niektórych problemów.$\mathsf{P}$$\mathsf{L}$

Istnieje jednak różnica między i L : podczas gdy czas wielomianowy P jest zdefiniowany jako połączenie problemów, które biegną w czasie O ( n k ) dla dowolnej stałej k , to znaczy:$\mathsf{P}$$\mathsf{L}$$\mathsf{P}$$O(n^k)$$k$

,$\mathsf{P} = \bigcup_{k \geq 0} \mathsf{TIME[n^k]}$

przestrzeń logów jest zdefiniowana jako S P A C E [ log n ] . Jeśli naśladujemy definicję P , staje się$\mathsf{L}$$\mathsf{SPACE[\log n]}$$\mathsf{P}$

,$\mathsf{PolyL} = \bigcup_{k \geq 0} \mathsf{SPACE[\log^k n]}$

gdzie nazywa się klasą przestrzeni polilogu . Moje pytanie brzmi:$\mathsf{PolyL}$

Dlaczego używamy przestrzeni dziennika jako pojęcia wydajnego obliczenia zamiast przestrzeni polilogu?

Jednym z głównych problemów mogą być kompletne zestawy problemów. W obszarze logarytmicznym wielokrotne redukcje, zarówno , jak i L mają całkowite problemy. W przeciwieństwie do tego, jeśli P O l a L ma pełną problemów wynikających redukcji, wówczas będzie miał w sprzeczności z twierdzeniem miejsce hierarchii. Ale co, jeśli przeszlibyśmy na redukcje polilogu? Czy możemy uniknąć takich problemów? W ogóle, jeśli staramy się jak najlepiej pasuje P o l y L pod pojęciem efektywności oraz (jeśli to konieczne) modyfikować niektóre definicje, aby uzyskać co dobre właściwości jest „ładny” klasa powinna mieć, jak daleko możemy pójść?$\mathsf{P}$$\mathsf{L}$$\mathsf{PolyL}$$\mathsf{PolyL}$

Czy istnieją jakieś teoretyczne i / lub praktyczne powody używania przestrzeni logów zamiast przestrzeni polilogu?

Najmniejszą klasą zawierającą czas liniowy i zamkniętą podprogramami jest P. Najmniejszą klasą zawierającą przestrzeń logową i zamkniętą podprogramami jest nadal przestrzeń logowa. Zatem P i L są najmniejszymi solidnymi klasami odpowiednio dla czasu i przestrzeni, dlatego są odpowiednie do modelowania wydajnych obliczeń.

$\text{SPACE}[\log^2 n] \subseteq \text{P}$$\log^{k-1}(n)$$\text{NSPACE}$$[\log^k n]$$\text{-complete}$

$\text{PLOSS} = \bigcup_k \text{TISP}[n^k, k \, \log^2 n]$$\text{DCFL} \subseteq \text{PLOSS}$$\text{SC}^2$$\text{SC}^k$

$2^{O(\log n)} = \operatorname{poly}(n)$

$\text{NSPACE}[\log^k n] \subseteq \text{SPACE}[\log^{2k}n]$

$\text{SC}^k = \text{TISP}[\operatorname{poly}(n), \log^k n]$

Myślę, że wszystkie pozostałe odpowiedzi są bardzo dobre; Spróbuję dać inne spojrzenie na ten problem.

Nie wiem, jak dobrze P modeluje „wydajne” obliczenia w prawdziwym świecie, ale podoba nam się ta klasa ze względu na dobre właściwości zamykania i inne matematyczne powody. Podobnie L jest także fajną klasą z powodu niektórych z wyżej wymienionych powodów.

Jednak, jak skomentowałeś, jeśli rozluźnimy naszą definicję „wydajnego” do quasi-wielomianowego czasu, wówczas PolyL jest również skuteczny. Możemy omówić teorię złożoności, w której pozwalamy klasom zdefiniowanym logarytmicznie związanym z niektórymi zasobami na używanie zasobów polilogu. Odpowiednio rozluźnilibyśmy również nasze definicje NC, NL itp., Aby zamiast tego umożliwić quasi-wielomianowe obwody wielkości. Jeśli to zrobimy, NC ₁ , L, NL i NC wszystkie pokrywają się z klasą PolyL. W tym sensie PolyL jest solidną klasą, ponieważ pokrywa się z nią wiele klas naturalnych. Aby uzyskać więcej informacji na temat teorii złożoności z log -> polilog i wielomian -> quasi-wielomian, zobacz Klasy obwodów wielkości quasipolynomial według Barringtona.

Innym powodem do studiowania poliL lub podobnych klas, takich jak quasi-AC _0, jest to, że chociaż separacja wyroczni między (powiedzmy) ParityP i PH sugeruje, że PARITY nie jest zawarta w AC ₀ , odwrotna implikacja nie jest znana. Z drugiej strony, PARYSTETNOŚĆ nie jest zawarta w quasi-AC ₀ wtedy i tylko wtedy, gdy istnieje separacja wyroczni między ParityP i PH. Podobnie klasy quasi-TC ₀ i quasi-AC ₀ są różne wtedy i tylko wtedy, gdy istnieje wyrocznia między CH i PH. Tak więc zwykłe klasy złożoności, takie jak PH, ModPH, CH itp., Po zmniejszeniu wykładniczym w celu udowodnienia wyników wyroczni zamieniają się w quasi-wielomianowe wersje zwykłych klas AC ₀ , ACC ₀ i TCOdpowiednio ₀ . Podobnie, argument użyty w twierdzeniu Tody (PH jest zawarty w P ^PP ) może zostać wykorzystany do wykazania, że ​​quasi-AC ₀ jest zawarty w głębokości-3 quasi-TC ₀ . (Nie wiem, czy ten sam wniosek jest znany dla zwykłych wersji tych klas. Widziałem to jako otwarty problem w niektórych artykułach).