NL (сложеност)

У рачунарској теорији сложености, NL (Недетерминистички логаритамски простор) класа сложености је која садржи проблеме одлучивости који могу да буду решени помоћу недетерминистичке Тјурингове машине, коришћењем логаритамске величине меморије.

NL је генерализација L, класе logspace проблема на детерминистичкој Тјуринговој машини. Пошто је свака детерминистичка Тјурингова машина истовремено и недетерминистичка, имамо да се L садржи у NL. NL може формално да се дефинише појмом недетерминистичког простора рачунарских ресурса (NSPACE) као NL = NSPACE(log n).

Важни резултати теорије сложености нам дозвољавају да направимо релацију између ове класе сложености и осталих, и дају нам податке о релативном утицају потребних ресурса. Са друге стране, резултати у области алгоритама, говоре нам о томе који проблеми могу да буду решени са датим ресурсима. Као што је случај и са већим делом теорије сложености, многа важна питања о NL су и даље отворена (погледај Нерешени проблеми у рачунарству). Понекад се NL замењује са RL, због пробабилистичке дефиниције која је приказана ниже. Ипак, назив RL се чешће користи за рандомизовани логаритамски простор, за који није познато да је једнак NL.

NL – комплетни проблеми

За неколико проблема је познато да су NL – комплетни уз logspace свођења, укључујући ST-повезаност и 2-изводљивост. ST-повезаност тражи чворове S и T усмереног графа и утврђује да ли постоји путања од S до T. 2-изводљивост у задатој формули у којој је сваки израз дисјункција два литерала, тражи да ли постоји вредност промењљиве за коју је формула тачна. Пример где означава негацију може да буде следећи:

$(x_{1}\vee \neg x_{3})\wedge (\neg x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \neg x_{2})$

Ограничења

Познато је да се NL садржи у P пошто постоји алгоритам полиномијалног времена за 2-изводљивост, али се не зна да ли је NL = P или L = NL. Зна се да је NL = co-NL, где је co-NL класа језика чији су комплементи у NL. Ово су независно открили Најл Имерман и Роберт Селепчењи 1987. Године (теорема Имермана и Селепчењија) који су 1995. године за свој рад добили Геделову награду У теорији сложености кола, NL може да се постави у NC хијерархију. У раду који је 1994. године објавио Пападимитриу, у теореми 16.1 имамо:

$\mathbf {NC} _{1}\subseteq \mathbf {L} \subseteq \mathbf {NL} \subseteq \mathbf {NC} _{2}.$

Тачније NL се садржи у AC. Познато је да је NL једнак ZPL, класи проблема који се, без грешке, решавају рандомизованим алгоритмима у логаритамском простору и неограниченом времену.

Ипак се не зна да ли је NL једнак RLP или ZPLP рестрикцијама RL и ZPL у полиномијалном времену, које неки аутори означавају као RL и ZPL. NL се може ставити у везу са детерминистичким простором коришћењем теореме Севича која нам говори да било који недетерминистички алгоритам може да се симулира на детерминистичкој машини у највише на квадрат већем простору. Непосредно из Севичеве теореме имамо да је:

$\mathbf {NL\subseteq SPACE} (\log ^{2}n)\ \ \ \ {\text{equivalently, }}\mathbf {NL\subseteq L} ^{2}.$

Ово је било најјаче укључење детерминистичког простора познато после 1994. године (Пападимитриу 1994. Проблем 16.4.10. „Симетрични простор“). Пошто на класе већег простора не утиче квадратно повећање, недетерминистичке и детерминистичке класе су једнаке. Тако је, на пример, PSPACE = NPSPACE.

Пробабилистичка дефиниција

Претпоставимо да је C класа сложености проблема одлучивања, који су решиви у логаритамском простору на пробабилистичким Тјуринговим машинама које никада не прихватају погрешне улазе, али им је дозвољено да погрешно одбаце исправне улазе у току мање од 1/3 времена обраде. Ово се зове једнострана грешка (one-sided error). Константа 1/3 је произвољна тако да ћемо рећи: за свако x, за које важи 0 ≤ x < 1/2.

Испоставља се да је C = NL. Приметимо да C, за разлику од одговарајуће детерминистичке класе L није ограничена полиномијалним временом зато што, иако има полиномијални број конфигурација може да користи случајност да би избегла бесконачну петљу. Ако је ограничимо на полиномијално време, добијамо класу RL која је садржана у NL, али није познато да ли јој је и једнака. Постоји једноставан алгоритам који показује да је C = NL. Јасно је да се C садржи у NL, зато што:

• Ако низ не припада језику, оба их одбацују на свим путањама обраде.
• Ако је низ део језика, NL алгоритам га прихвата на најмање једној путањи обраде, а C алгоритам га прихвата дуж најмање две трећине својих путања обраде.

Да би показали да се NL садржи у C, једноставно ћемо узети NL алгоритам и одабрати случајну путању обраде дужине n, и то учинити 2ⁿ пута. Пошто ниједна путања обраде није дужа од n и зато што укупно постоје 2ⁿ путања, добре су шансе да се погоди она која прихвата улаз (ограничена одоздо константом). Једини проблем је што немамо простора и logspace-у за бинарни бројач који иде до 2ⁿ. Да би то решили заменићемо га рандомизованим бројачем, који једноставно баца n новчића и зауставља се и одбија улазе, ако новчићи падну на „главу“. Пошто овакав догађај има вероватноћу 2^-n, очекујемо у просеку 2ⁿ корака пре заустављања. Алгоритам треба само да памти текућу суму појава „глава“ у низу, коју може да ускладишти у logspace-у (логаритамском простору).

Пошто теорема Имермана и Селепчењија, по којој је NL затворена са допунама, једнострана грешка (one-sided error) у овим пробабилистичким обрадама може да буде замењена са „0-страном грешком“ (zero-sided error). То значи да ови проблеми могу да се реше помоћу пробабилистичких Тјурингових машина које користе логаритамски простор и никада не праве грешке. Одговарајућа класа сложености, која захтева од машине и да користи само полиномијално време, зове се ZPLP.

Тако, у случају када посматрамо само простор, делује да су рандомизација и недетерминизам приступи који дају подједнаке ефекте.

Дескриптивна (описна) сложеност

Постоји једноставна логичка карактеризација класе NL: она садржи тачно оне језике који се могу изразити првог реда са додатком оператора транзитивног затварања.

Референце

• Сипсер, Мајкл (1997). „Sections 8.4—8.6: The Classes L and NL, NL-completeness, NL equals coNL”. Introduction to the Theory of Computation. PWS Publishing. стр. 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).