L (složenost)
U računarskoj teoriji složenosti, L (poznata i kao LSPACE ili DLOGSPACE) je klasa složenosti koja sadrži probleme odlučivosti, koji mogu da budu rešeni pomoću determinističke Tjuringove mašine koja koristi logaritamsku količinu memorijskog prostora.[1][2] Logaritamski prostor je dovoljan da prihvati konstantan broj pokazivača na ulaze i logaritamski broj logičkih – Bulovih vrednosti. Mnogi osnovni logspace (logaritamski prostor) algoritmi koriste memoriju na isti način.
Kompletni problemi i logička karakterizacija uredi
Svaki netrivijalni problem iz L je kompletan primenom logspace svođenja[3]. Tako su manja svođenja dovoljna da bi se identifikovali smisleni pojmovi L – kompletnosti. Najčešća je upotreba svođenja prvog reda.
Rezultati Omera Rajngolda iz 2004. godine pokazuju da je USTCON (problem da li postoji putanja između dva čvora u zadatom neusmerenom grafu) u L, i pri tome, da je L = SL, pošto je USTCON SL – kompletan.
Jedna posledica toga je jednostavna logička karakterizacija L: L sadrži samo jezike koji se mogu opisati logikom prvog reda sa dodatnim kumulativnim operatorom tranzitivnog zatvaranja ( u smislu teorije grafova, ovo svaku povezanu komponentu pretvara u kliku). Ovaj rezultat ima sledeću primenu u jezicima za upite u bazama podataka : složenost podataka upita je definisana kao složenost odgovaranja na fiksni upit, pri čemu se dužina podataka posmatra kao ulazna promenljiva. Uzimajući u obzir ovu defiiniciju, upiti nad relacionim bazama podataka sa kompletnom informacijom ( ne uzimajući u obzir vrednosti nulls – prazna polja) , kao što je izraženo, na primer, u relacionoj algebri, su u L.
Srodne klase složenosti uredi
L je podklasa NL, koja je klasa jezika odlučivih u logaritamskom prostoru na nedeterminističkoj Tjuringovoj mašini. Problem u NL može se transformisati u problem dostupnosti čvorova kod usmerenog grafa koji predstavlja stanja i promene stanja nedetermiinističke mašine, dok granice logaritamskog prostora impliciraju da ovaj graf ima polinomni broj čvorova i stranica, iz čega sledi da je NL sadržan u klasi složenosti P problema koji su rešivi u determinističkom polinomijalnom vremenu.[4] Tako da važi L ⊆ NL ⊆ P. Činjenica da je L podskup P se može dokazati na drugi način koji je više direktan: odlučivač koji koristi O(log n) prostor ne može koristiti više od 2O(log n) = nO(1) vremena, jer je ovo totalni broj mogućih konfiguracija, L je takođe srodan klasi NC na sledeći način: NC1 ⊆ L ⊆ NL ⊆ NC², što znači da za dati paralelni kompjuter C sa polinomijalnim brojem O(nk) procesora za neko konstantno k, svaki problem koji se može rešiti na C za O(log n) vremena je u L, i svaki problem u L se može rešiti u O(log² n) vremena na C. Važni otvoreni problemi uključuju da li je L = P,[2] and whether L = NL.[5].
Srodna klasa problema funkcija je FL. FL se često koristi za definisanje redukcija u logaritamskom prostoru.
Dodatne osobine uredi
L je nisko samo za sebe, zato što može da simulira proročke upite iz logaritamskog prostora ( grubo govoreći, „ pozivi funkcija koje koriste logaritamski prostor“) iznova koristeći isti prostor za svaki upit.
Ostale primene uredi
Glavna ideja korišćenja logaritamskog prostora je to da se broj sa polinomijalnom amplitudom može skladištiti u logaritamskom prostoru i koristiti za pamćenje pokazivača na poziciji ulaza.
Iz ovog razloga, klasa u logaritamskom prostoru je korisna za modelovanje računarske obrade kod koje je ulaz previše velik da bi stao u operativnu memoriju kompjutera. Dugački nizovi DNK i baze podataka su dobri primeri problema kod kojih će samo konstantan deo ulaza biti u operativnu memoriji u datom vremenu i kod kojih imamo pokazivače za obradu sledećeg dela ulaza, koristeći samo logaritamsku memoriju.
Reference uredi
- ^ Sipser 1997, Definition 8.12. str. 295.
- ^ a b Garey & Johnson 1979, str. 177
- ^ See Garey & Johnson 1979, Theorem 7.13 (claim 2). str. 179.
- ^ Sipser 1997, Corollary 8.21. str. 299.
- ^ Sipser 1997, str. 297; Garey & Johnson 1979, str. 180