L (složitost) - L (complexity) - Wikipedia
v teorie výpočetní složitosti, L (také známý jako LSPACE nebo DLOGSPACE) je třída složitosti obsahující rozhodovací problémy to může vyřešit a deterministický Turingův stroj používat logaritmický množství zapisovatelného paměťový prostor.[1][2] Formálně má Turingův stroj dvě pásky, z nichž jedna kóduje vstup a lze ji pouze číst, zatímco druhá páska má logaritmickou velikost, ale lze ji číst i zapisovat. Logaritmický prostor je dostatečný k udržení konstantního počtu ukazatele do vstupu[1] a logaritmický počet logických příznaků a mnoho základních algoritmů logspace využívá paměť tímto způsobem.
Kompletní problémy a logická charakterizace
Každý netriviální problém v L je kompletní pod redukce log prostoru,[3] k identifikaci smysluplných pojmů je zapotřebí slabší redukce L- úplnost, nejběžnější bytost první objednávka redukce.
Výsledek za rok 2004 Omer Reingold ukázat to USTCON, problém, zda existuje cesta mezi dvěma vrcholy v daném neorientovaný graf, je v L, což ukazuje L = SL, protože USTCON je SL-kompletní.[4]
Důsledkem toho je jednoduchá logická charakterizace L: obsahuje přesně ty jazyky, které jsou vyjádřitelné v logika prvního řádu s přidaným komutativem přechodné uzavření operátor (v graf teoretický pojmy, to se obrací každý připojená součást do klika ). Tento výsledek má aplikaci na databázi dotazovací jazyky: složitost dat dotazu je definována jako složitost odpovědi na pevný dotaz s ohledem na velikost dat jako vstup proměnné. U tohoto opatření dotazy proti relační databáze s úplnými informacemi (nemají pojem nuly ), jak je vyjádřeno například v relační algebra jsou v L.
Související třídy složitosti
L je podtřída NL, což je třída jazyků, v nichž lze rozhodnout logaritmický prostor na a nedeterministický Turingův stroj. Problém v NL může být přeměněn na problém dosažitelnost v řízený graf reprezentující stavy a přechody stavů nedeterministického stroje a z logaritmického vázaného prostoru vyplývá, že tento graf má polynomický počet vrcholů a hran, ze kterých vyplývá, že NL je obsažen ve třídě složitosti P problémů řešitelných v deterministickém polynomiálním čase.[5] Tím pádem L ⊆ NL ⊆ P. Zahrnutí L do P lze také dokázat příměji: rozhodování pomocí Ó(logn) V prostoru nelze použít více než 2Ó(logn) = nÓ(1) čas, protože toto je celkový počet možných konfigurací.
L dále se týká třídy NC následujícím způsobem:NC1 ⊆ L ⊆ NL ⊆ NC2Slovy, vzhledem k paralelnímu počítači C s polynomickým číslem Ó(nk) procesorů pro nějakou konstantu k, jakýkoli problém, který lze vyřešit C v Ó(logn) nastal čas La jakýkoli problém v L lze vyřešit v Ó(log2 n) čas C.
Důležité otevřené problémy zahrnout zda L = P,[2] a zda L = NL.[6] Není ani známo, zda L = NP.[7]
Související třída funkční problémy je FL. FL se často používá k definování redukce logspace.
Další vlastnosti
L je nízký pro sebe, protože dokáže simulovat věštecké dotazy log-prostoru (zhruba řečeno „volání funkcí, která používají logovací prostor“) v logovém prostoru, přičemž pro každý dotaz znovu použije stejný prostor.
Jiná použití
Hlavní myšlenkou logspace je, že lze v logspace uložit číslo polynomiální velikosti a použít ho k zapamatování ukazatelů na pozici vstupu.
Třída logspace je proto užitečná pro modelování výpočtu, kde je vstup příliš velký na to, aby se do něj vešel RAM počítače. Dlouho DNA sekvence a databáze jsou dobrým příkladem problémů, kdy v daném čase bude v paměti RAM pouze konstantní část vstupu a kde máme ukazatele pro výpočet další části vstupu ke kontrole, tedy s využitím pouze logaritmické paměti.
Viz také
- L / poly, nejednotná varianta L, která zachycuje složitost velikosti polynomu větvící programy
Poznámky
- ^ A b Sipser (1997), Definice 8.12, s. 295.
- ^ A b Garey & Johnson (1979), str. 177.
- ^ Vidět Garey & Johnson (1979), Věta 7.13 (nárok 2), s. 179.
- ^ Reingold, Omer (2005). Neusměrněná konektivita ST v logovém prostoru. STOC'05: Proceedings of the 37.th Annual ACM Symposium on Theory of Computing. ACM, New York. 376–385. doi:10.1145/1060590.1060647. PAN 2181639. ECCC TR04-094.
- ^ Sipser (1997), Dodatek 8,21, s. 299.
- ^ Sipser (1997), str. 297; Garey & Johnson (1979), str. 180.
- ^ https://cs.stackexchange.com/questions/103073/is-it-possible-that-l-np
Reference
- Arora, Sanjeev; Barak, Boaz (2009). Výpočetní složitost. Moderní přístup. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.
- Papadimitriou, Christos (1993). Výpočetní složitost (1. vyd.). Addison Wesley. Kapitola 16: Logaritmický prostor, str. 395–408. ISBN 0-201-53082-1.
- Sipser, Michael (1997). Úvod do teorie výpočtu. PWS Publishing. Oddíl 8.4: Třídy L a NL, s. 294–296. ISBN 0-534-94728-X.
- Garey, M.R.; Johnson, D.S. (1979). Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti. W.H. Freemane. Část 7.5: Logaritmický prostor, s. 177–181. ISBN 0-7167-1045-5.
- Cook, Stephen A.; McKenzie, Pierre (1987). „Problémy vyřešeny pro deterministický logaritmický prostor“ (PDF). Journal of Algorithms. 8 (3): 385–394. doi:10.1016/0196-6774(87)90018-6. ISSN 0196-6774.