L (složitost)

V teoretické informatice , a zejména v teorii složitosti , je třída L třídou rozhodovacích problémů, o které rozhoduje deterministický Turingův stroj, který využívá prostor logaritmické velikosti jako funkci velikosti vstupu. Přesněji řečeno, požadavek na prostor logaritmické velikosti odkazuje na další využitelný prostor. To je také někdy uvedeno LOGSPACE .

Tato třída intuitivně obsahuje problémy, o kterých lze rozhodnout s konstantním počtem ukazatelů na paměťové buňky vstupu problému a konstantním počtem dalších dat (čítače, jejichž hodnoty jsou mezi 0 a polynomickou veličinou ve velikosti vstupu, booleovci atd.).

Formální definice

Pokud zavoláme množinu všech problémů, o nichž rozhodují deterministické Turingovy stroje využívající prostor (kromě vstupu) pro funkci o velikosti vstupu , pak můžeme formálně definovat L pomocí: $\ mbox {SPACE} (t (n))$ $O (t (n))$ $t$ $ne$

${\ mbox {L}} = {\ mbox {SPACE}} (\ log (n)) \.$

Příklady problémů

Příklady jazyků

Jazyk je v L . Zde je algoritmus, který rozhoduje v logaritmickém prostoru: ${\ displaystyle \ {0 ^ {k} 1 ^ {k} \ střední k \ v \ mathbb {N} \}}$ ${\ displaystyle \ {0 ^ {k} 1 ^ {k} \ střední k \ v \ mathbb {N} \}}$

procedure M(w) si w vide accepter i = 0 tant que w[i] == 0 i := i+1 compteurzero := i tant que w[i] == 1 i := i+1 si w[i] != ' ' (différent de la fin de mot) refuser si compteurzero == (i - compteurzero) accepter sinon refuser

Slovo w se nemění: je to položka a do výpočtu použité paměti se nezapočítává. Počítáme pouze další paměť, jmenovitě proměnné i a counterzero, což jsou kladná celá čísla ohraničená | w | a že můžeme kódovat v logaritmickém prostoru v | w |.

Jazyk slov generovaných následující algebraickou gramatikou je v L: S -> (S) | SS | ε.

Násobení

Binární reprezentace celého čísla je uvedena v této části. Jazyk je v L . Následující algoritmus rozpozná použití mezery v , kde je velikost jeho vstupu. Algoritmus bere jako vstup tři celá čísla n , ma p ověří, že násobení n o m je skutečně p . Vypočítává při každé iteraci i- tý bit výsledku násobení a porovnává jej s i - tým bitem p. $ne$ ${\ displaystyle \ langle n \ rangle}$ ${\ displaystyle \ mathrm {MULT} = \ left \ {(\ langle n \ rangle, \ langle m \ rangle, \ langle n \ times m \ rangle) \ mid n, m \ in \ mathbb {N} \ right \ }}$ ${\ displaystyle \ mathrm {MULT}}$ ${\ displaystyle {\ mathcal {O}} (\ log T)}$ $T$

V popisu algoritmu se používají následující postupy:

přírůstek ( x ), zvýší proměnnou x ;
est_un ( x , i ), označuje, zda i- tý bit x není nula, pokud i je větší než velikost x, je bit považován za nulu;
divide_by_two ( x ), nahradí x podílem svého euklidovského dělení 2; toto může být implementováno jako bitový posun x z jedné na nejméně významné bity.

procedure verifierMultiplication(n, m, p) retenue = 0 i = 0 tant que i < max(|n| + |m| - 1, |p|) j = 0 tant que j < i k = 0 tant que k + j <= i si est_un(n, j) et est_un(m, k) incrémenter(retenue) k := k + 1 si p[i] != retenue[0] rejeter diviser_par_deux(retenue) j := j + 1 i := i + 1 accepter

Hodnota použitých čítačů i , j a k nepřesahuje velikost záznamu, a proto ji lze logaritmicky kódovat do velikosti záznamu. Zavedené postupy a srovnání používají maximálně jeden logaritmický prostor ve velikosti záznamu. Nakonec hodnota vybrané proměnné nesmí překročit , lze ji proto kódovat na mezeru v . ${\ displaystyle \ max \ left (| n | + | m | -1, | p | \ right) ^ {3} <T ^ {3}}$ ${\ displaystyle {\ mathcal {O}} \ vlevo (3 \ log T \ vpravo)}$

Vztahy s jinými třídami složitosti

Známe následující inkluze:

NC 1 ⊆ L ⊆ NL ⊆ AC 1 ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE

Je také známo, že zařazení L do PSPACE je přísné, takže jedna z výše uvedených inkluzí je přísná. Není nemožné, aby byli všichni .

Třída SL a problém s přístupností v neorientovaném grafu

Lewis a Christos Papadimitriou definovali v roce 1982 „symetrickou“ variantu L: třídu SL (pro symetrický logoprostor v angličtině). Původní definice používá pojem symetrický Turingův stroj namísto klasických deterministických Turingových strojů. Ekvivalentně je SL třída problémů, o nichž rozhoduje nedeterministický Turingův stroj v logaritmickém prostoru, s následujícím omezením symetrie:

Pokud může stroj přejít z konfigurace A do konfigurace B, pak může také přejít z konfigurace B do konfigurace A.

Třída SL je tedy mezi L a NL . Lewis a Papadimitriou ukázali, že problém s přístupností v neorientovaném grafu je SL-complete (pro logaritmické redukce ). Tento problém s přístupností bere jako vstup neorientovaný graf, vrchol s a vrchol t a určuje, zda existuje cesta od daného vrcholu s k danému vrcholu t (všimněte si, že verze problému přístupnosti pro orientované grafy je úplná NL ).

V roce 2004 Omer Reingold ukazuje, že o problému přístupnosti v neorientovaném grafu se rozhoduje v logaritmickém prostoru na deterministickém stroji, a proto, že L = SL . Reingoldův důkaz používá pojem expanzních grafů . Tento výsledek mu v roce 2009 vynesl Gödelovu cenu .

Poznámky a odkazy

Garey a Johnson 1979 , str. 177 .
Sipser 1997 , definice 8.12, s. 295 .
Michael Sipser , Úvod do teorie výpočtu , International Thomson Publishing,1 st 12. 1996, 396 s. ( ISBN 0-534-94728-X , číst online ) , s. 349, příklad 8.18
(in) Dexter C. Kozen, Theory of Computation , domácí úkoly 3. Př. 1. str. 277
Michael Sipser , Úvod do teorie výpočtu , International Thomson Publishing,1 st 12. 1996, 396 s. ( ISBN 0-534-94728-X , číst online ) , s. 359, Př. 8.20
Omer Reingold , Salil Vadhan a Avi Wigderson , „ Entropické vlny, produkt grafu cik-cak a nové expandéry konstantního stupně “, Annals of Mathematics , sv. 155, n o 1,2002, str. 157–187 ( DOI 10.2307 / 3062153 , JSTOR 3062153 , Math Reviews 1888797 , číst online )
Omer Reingold , „ Neusměrněná konektivita v logovém prostoru, “ Journal of the ACM , vol. 55, n O 4,2008, str. 1–24 ( číst online )

Bibliografie

(en) Sanjeev Arora a Boaz Barak , Výpočetní složitost: moderní přístup , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , kap. 1 („Výpočtový model - a proč na tom nezáleží“)
Omer Reingold , „ neřízený ST-konektivita Přihlášení Space “, Electronic kolokvium o výpočetní složitosti , n o 94,2004( číst online ). Elektronická verze.
Omer Reingold , „ Neusměrněné připojení v logovém prostoru “, Journal of the ACM , sv. 55, n O 4,2008, str. 1–24 ( DOI 10.1145 / 1391289.1391291 , matematické recenze 2445014 ). Verze deníku.
(en) MR Garey a DS Johnson , Počítače a neřešitelnost: průvodce teorií NP-úplnosti , New York, WH Freeman,1979, 338 s. ( ISBN 0-7167-1045-5 ) , oddíl 7.5: Logaritmický prostor, str. 177–181
(en) Christos Papadimitriou , Výpočetní složitost , Čtení (mše), Addison Wesley,1993, 1. vyd. , 523 s. ( ISBN 0-201-53082-1 ) , str. Kapitola 16: Logaritmický prostor, str. 395-408
(en) Michael Sipser , Úvod do teorie výpočtu , PWS Publishing,1997, 396 s. ( ISBN 0-534-94728-X ) , oddíl 8.4: Třídy L a NL, str. 294–296

externí odkazy

(cs) Třída L v ZOO Složitosti
(fr) Třída SL v Zoo Complexity