NL (složenost)

Iz Vikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu

U računarskoj teoriji složenosti, NL (Nedeterministički logaritamski prostor) klasa složenosti je koja sadrži probleme odlučivosti koji mogu da budu rešeni pomoću nedeterminističke Tjuringove mašine, korišćenjem logaritamske veličine memorije.

NL je generalizacija L, klase logspace problema na determinističkoj Tjuringovoj mašini. Pošto je svaka deterministička Tjuringova mašina istovremeno i nedeterministička, imamo da se L sadrži u NL. NL može formalno da se definiše pojmom nedeterminističkog prostora računarskih resursa (NSPACE) kao NL = NSPACE(log n).

Važni rezultati teorije složenosti nam dozvoljavaju da napravimo relaciju između ove klase složenosti i ostalih, i daju nam podatke o relativnom uticaju potrebnih resursa. Sa druge strane, rezultati u oblasti algoritama, govore nam o tome koji problemi mogu da budu rešeni sa datim resursima. Kao što je slučaj i sa većim delom teorije složenosti, mnoga važna pitanja o NL su i dalje otvorena (pogledaj Nerešeni problemi u računarstvu). Ponekad se NL zamenjuje sa RL, zbog probabilističke definicije koja je prikazana niže. Ipak, naziv RL se češće koristi za randomizovani logaritamski prostor, za koji nije poznato da je jednak NL.

NL – kompletni problemi[uredi]

Za nekoliko problema je poznato da su NL – kompletni uz logspace svođenja, uključujući ST-povezanost i 2-izvodljivost. ST-povezanost traži čvorove S i T usmerenog grafa i utvrđuje da li postoji putanja od S do T. 2-izvodljivost u zadatoj formuli u kojoj je svaki izraz disjunkcija dva literala, traži da li postoji vrednost promenjljive za koju je formula tačna. Primer gde označava negaciju može da bude sledeći:

Ograničenja[uredi]

Poznato je da se NL sadrži u P pošto postoji algoritam polinomijalnog vremena za 2-izvodljivost, ali se ne zna da li je NL = P ili L = NL. Zna se da je NL = co-NL, gde je co-NL klasa jezika čiji su komplementi u NL. Ovo su nezavisno otkrili Najl Imerman i Robert Selepčenji 1987. Godine (teorema Imermana i Selepčenjija) koji su 1995. godine za svoj rad dobili Gedelovu nagradu U teoriji složenosti kola, NL može da se postavi u NC hijerarhiju. U radu koji je 1994. godine objavio Papadimitriu, u teoremi 16.1 imamo:

Tačnije NL se sadrži u AC. Poznato je da je NL jednak ZPL, klasi problema koji se, bez greške, rešavaju randomizovanim algoritmima u logaritamskom prostoru i neograničenom vremenu.

Ipak se ne zna da li je NL jednak RLP ili ZPLP restrikcijama RL i ZPL u polinomijalnom vremenu, koje neki autori označavaju kao RL i ZPL. NL se može staviti u vezu sa determinističkim prostorom korišćenjem teoreme Seviča koja nam govori da bilo koji nedeterministički algoritam može da se simulira na determinističkoj mašini u najviše na kvadrat većem prostoru. Neposredno iz Sevičeve teoreme imamo da je:

Ovo je bilo najjače uključenje determinističkog prostora poznato posle 1994. godine (Papadimitriu 1994. Problem 16.4.10. „Simetrični prostor“). Pošto na klase većeg prostora ne utiče kvadratno povećanje, nedeterminističke i determinističke klase su jednake. Tako je, na primer, PSPACE = NPSPACE.

Probabilistička definicija[uredi]

Pretpostavimo da je C klasa složenosti problema odlučivanja, koji su rešivi u logaritamskom prostoru na probabilističkim Tjuringovim mašinama koje nikada ne prihvataju pogrešne ulaze, ali im je dozvoljeno da pogrešno odbace ispravne ulaze u toku manje od 1/3 vremena obrade. Ovo se zove jednostrana greška (one-sided error). Konstanta 1/3 je proizvoljna tako da ćemo reći: za svako x, za koje važi 0 ≤ x < 1/2.

Ispostavlja se da je C = NL. Primetimo da C, za razliku od odgovarajuće determinističke klase L nije ograničena polinomijalnim vremenom zato što, iako ima polinomijalni broj konfiguracija može da koristi slučajnost da bi izbegla beskonačnu petlju. Ako je ograničimo na polinomijalno vreme, dobijamo klasu RL koja je sadržana u NL, ali nije poznato da li joj je i jednaka. Postoji jednostavan algoritam koji pokazuje da je C = NL. Jasno je da se C sadrži u NL, zato što:

  • Ako niz ne pripada jeziku, oba ih odbacuju na svim putanjama obrade.
  • Ako je niz deo jezika, NL algoritam ga prihvata na najmanje jednoj putanji obrade, a C algoritam ga prihvata duž najmanje dve trećine svojih putanja obrade.

Da bi pokazali da se NL sadrži u C, jednostavno ćemo uzeti NL algoritam i odabrati slučajnu putanju obrade dužine n, i to učiniti 2n puta. Pošto nijedna putanja obrade nije duža od n i zato što ukupno postoje 2n putanja, dobre su šanse da se pogodi ona koja prihvata ulaz (ograničena odozdo konstantom). Jedini problem je što nemamo prostora i logspace-u za binarni brojač koji ide do 2n. Da bi to rešili zamenićemo ga randomizovanim brojačem, koji jednostavno baca n novčića i zaustavlja se i odbija ulaze, ako novčići padnu na „glavu“. Pošto ovakav događaj ima verovatnoću 2-n, očekujemo u proseku 2n koraka pre zaustavljanja. Algoritam treba samo da pamti tekuću sumu pojava „glava“ u nizu, koju može da uskladišti u logspace-u (logaritamskom prostoru).

Pošto teorema Imermana i Selepčenjija, po kojoj je NL zatvorena sa dopunama, jednostrana greška (one-sided error) u ovim probabilističkim obradama može da bude zamenjena sa „0-stranom greškom“ (zero-sided error). To znači da ovi problemi mogu da se reše pomoću probabilističkih Tjuringovih mašina koje koriste logaritamski prostor i nikada ne prave greške. Odgovarajuća klasa složenosti, koja zahteva od mašine i da koristi samo polinomijalno vreme, zove se ZPLP.

Tako, u slučaju kada posmatramo samo prostor, deluje da su randomizacija i nedeterminizam pristupi koji daju podjednake efekte.

Deskriptivna (opisna) složenost[uredi]

Postoji jednostavna logička karakterizacija klase NL: ona sadrži tačno one jezike koji se mogu izraziti prvog reda sa dodatkom operatora tranzitivnog zatvaranja.

Reference[uredi]

  • Sipser, Majkl (1997). „Sections 8.4—8.6: The Classes L and NL, NL-completeness, NL equals coNL”. Introduction to the Theory of Computation. PWS Publishing. str. 294—302. ISBN 978-0-534-94728-6. 
  • Introduction to Complexity Theory: Lecture 7. Oded Goldreich. Proposition 6.1. Our C is what Goldreich calls badRSPACE(log n).