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


49

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.PL

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:PLPO(nk)k

,P=k0TIME[nk]

przestrzeń logów jest zdefiniowana jako S P A C E [ log n ] . Jeśli naśladujemy definicję P , staje sięLSPACE[logn]P

,PolyL=k0SPACE[logkn]

gdzie nazywa się klasą przestrzeni polilogu . Moje pytanie brzmi: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ść?PLPolyLPolyL

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


Hsien-Chih, ładne pytanie.
Mohammad Al-Turkistany

9
polyLPPpolyLpolyLP polyLpolyL, możesz sprawdzić podręcznik złożoności Papadimitriou , w szczególności ćwiczenia i dyskusję na końcu rozdziału 16.
Daniel Apon

polyLP

P

P

Odpowiedzi:


51

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ń.


4
To wygląda na najlepszą odpowiedź na zadane pytanie.
Derrick Stolee,

1
Spośród tych wszystkich dobrych odpowiedzi uważam, że odpowiedź Lance'a jest najbardziej precyzyjna i zaakceptuję ją. Ale wciąż wiele dzięki każdej przemyślanej odpowiedzi!
Hsien-Chih Chang 之 之

1
Problemem jest również to, czy P = L.
Diego de Estrada,

25

SPACE[log2n]Plogk1(n)NSPACE[logkn]-complete

PLOSS=kTISP[nk,klog2n]DCFLPLOSSSC2SCk


2
QuasiP=k0TIME[2logkn]P

Czy jest to znany otwarty problem? Czy możesz podać referencje?
Mohammad Al-Turkistany

SC2

5
Zauważ, że SC został nazwany przez Nicka Pippengera, w rzekomo wzajemnej umowie ze Stevem Cookiem, aby nazwać NC po nim :)
Suresh Venkat

PPQuasiPpolyLLPSPACE[logkn]PkLk
Hsien-Chih Chang 之 之

20

2O(logn)=poly(n)

NSPACE[logkn]SPACE[log2kn]

SCk=TISP[poly(n),logkn]


polyLNLpolyL

{1}

Masz rację, przepraszam za głupie pytanie :(
Hsien-Chih Chang 張顯 之

13

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 1 , 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 0 , odwrotna implikacja nie jest znana. Z drugiej strony, PARYSTETNOŚĆ nie jest zawarta w quasi-AC 0 wtedy i tylko wtedy, gdy istnieje separacja wyroczni między ParityP i PH. Podobnie klasy quasi-TC 0 i quasi-AC 0 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 0 , ACC 0 i TCOdpowiednio 0 . Podobnie, argument użyty w twierdzeniu Tody (PH jest zawarty w P PP ) może zostać wykorzystany do wykazania, że ​​quasi-AC 0 jest zawarty w głębokości-3 quasi-TC 0 . (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).


1
Twoja odpowiedź naprawdę pomaga, dziękuję za podzielenie się swoją opinią. Dziwię się, że Quasi-coś zostało DUŻO przestudiowane !!
Hsien-Chih Chang 之 之
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.