Пређи на садржај

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] Тако да важи LNLP. Чињеница да је L подскуп P се може доказати на други начин који је више директан: одлучивач који користи O(log n) простор не може користити више од 2O(log n) = nO(1) времена, јер је ово тотални број могућих конфигурација, L је такође сродан класи NC на следећи начин: NC1LNLNC², што значи да за дати паралелни компјутер 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 је ниско само за себе, зато што може да симулира пророчке упите из логаритамског простора ( грубо говорећи, „ позиви функција које користе логаритамски простор“) изнова користећи исти простор за сваки упит.

Остале примене

[уреди | уреди извор]

Главна идеја коришћења логаритамског простора је то да се број са полиномијалном амплитудом може складиштити у логаритамском простору и користити за памћење показивача на позицији улаза.

Из овог разлога, класа у логаритамском простору је корисна за моделовање рачунарске обраде код које је улаз превише велик да би стао у оперативну меморију компјутера. Дугачки низови ДНК и базе података су добри примери проблема код којих ће само константан део улаза бити у оперативну меморији у датом времену и код којих имамо показиваче за обраду следећег дела улаза, користећи само логаритамску меморију.

Референце

[уреди | уреди извор]
  1. ^ Sipser 1997, Definition 8.12. стр. 295.
  2. ^ а б Garey & Johnson 1979, стр. 177
  3. ^ See Garey & Johnson 1979, Theorem 7.13 (claim 2). стр. 179.
  4. ^ Sipser 1997, Corollary 8.21. стр. 299.
  5. ^ Sipser 1997, стр. 297; Garey & Johnson 1979, стр. 180