L (сложеност)
У рачунарској теорији сложености, L (позната и као LSPACE или DLOGSPACE) је класа сложености која садржи проблеме одлучивости, који могу да буду решени помоћу детерминистичке Тјурингове машине која користи логаритамску количину меморијског простора.[1][2] Логаритамски простор је довољан да прихвати константан број показивача на улазе и логаритамски број логичких – Булових вредности. Многи основни logspace (логаритамски простор) алгоритми користе меморију на исти начин.
Комплетни проблеми и логичка карактеризација уреди
Сваки нетривијални проблем из L је комплетан применом logspace свођења[3]. Тако су мања свођења довољна да би се идентификовали смислени појмови L – комплетности. Најчешћа је употреба свођења првог реда.
Rезултати Омера Рајнголда из 2004. године показују да је USTCON (проблем да ли постоји путања између два чвора у задатом неусмереном графу) у L, и при томе, да је L = SL, пошто је USTCON SL – комплетан.
Једна последица тога је једноставна логичка карактеризација L: L садржи само језике који се могу описати логиком првог реда са додатним кумулативним оператором транзитивног затварања ( у смислу теорије графова, ово сваку повезану компоненту претвара у клику). Овај резултат има следећу примену у језицима за упите у базама података : сложеност података упита је дефинисана као сложеност одговарања на фиксни упит, при чему се дужина података посматра као улазна променљива. Узимајући у обзир ову дефииницију, упити над релационим базама података са комплетном информацијом ( не узимајући у обзир вредности nulls – празна поља) , као што је изражено, на пример, у релационој алгебри, су у L.
Сродне класе сложености уреди
L је подкласа NL, која је класа језика одлучивих у логаритамском простору на недетерминистичкој Тјуринговој машини. Проблем у NL може се трансформисати у проблем доступности чворова код усмереног графа који представља стања и промене стања недетермиинистичке машине, док границе логаритамског простора имплицирају да овај граф има полиномни број чворова и страница, из чега следи да је NL садржан у класи сложености P проблема који су решиви у детерминистичком полиномијалном времену.[4] Тако да важи L ⊆ NL ⊆ P. Чињеница да је L подскуп P се може доказати на други начин који је више директан: одлучивач који користи O(log n) простор не може користити више од 2O(log n) = nO(1) времена, јер је ово тотални број могућих конфигурација, L је такође сродан класи NC на следећи начин: NC1 ⊆ L ⊆ NL ⊆ NC², што значи да за дати паралелни компјутер C са полиномијалним бројем O(nk) процесора за неко константно k, сваки проблем који се може решити на C за O(log n) времена је у L, и сваки проблем у L се може решити у O(log² n) времена на C. Важни отворени проблеми укључују да ли је L = P,[2] and whether L = NL.[5].
Сродна класа проблема функција је FL. FL се често користи за дефинисање редукција у логаритамском простору.
Додатне особине уреди
L је ниско само за себе, зато што може да симулира пророчке упите из логаритамског простора ( грубо говорећи, „ позиви функција које користе логаритамски простор“) изнова користећи исти простор за сваки упит.
Остале примене уреди
Главна идеја коришћења логаритамског простора је то да се број са полиномијалном амплитудом може складиштити у логаритамском простору и користити за памћење показивача на позицији улаза.
Из овог разлога, класа у логаритамском простору је корисна за моделовање рачунарске обраде код које је улаз превише велик да би стао у оперативну меморију компјутера. Дугачки низови ДНК и базе података су добри примери проблема код којих ће само константан део улаза бити у оперативну меморији у датом времену и код којих имамо показиваче за обраду следећег дела улаза, користећи само логаритамску меморију.
Референце уреди
- ^ Sipser 1997, Definition 8.12. стр. 295.
- ^ а б Garey & Johnson 1979, стр. 177
- ^ See Garey & Johnson 1979, Theorem 7.13 (claim 2). стр. 179.
- ^ Sipser 1997, Corollary 8.21. стр. 299.
- ^ Sipser 1997, стр. 297; Garey & Johnson 1979, стр. 180