L (monimutkaisuus)

In tietojenkäsittelyteoria , ja erityisesti vaativuusteoria , luokka L on luokka päätöksen ongelmat ratkaistaan deterministinen Turingin kone , joka käyttää tila on logaritminen koko funktiona koko panos. Tarkemmin sanottuna logaritmisen kokotilan vaatimus viittaa käytettävissä olevaan lisätilaan. Joskus todetaan myös LOGSPACE .

Intuitiivisesti tämä luokka sisältää ongelmat, jotka voidaan ratkaista vakiomäärällä osoituksia muistisoluille ongelman syötteestä ja vakiona lukuisalla lisätiedolla (laskurit, joiden arvot ovat 0: n ja polynomimäärän välillä syöttökoko, boolealaiset jne.).

Virallinen määritelmä

Jos kutsumme joukko kaikkia ongelmia, jotka deterministiset Turingin koneet päättävät käyttämällä välilyöntiä (syötteen lisäksi) tulon kokoiselle funktiolle , voimme määrittää L: n muodollisesti seuraavasti: Avaruus(t(ei)){\ displaystyle {\ mbox {SPACE}} (t (n))}} O(t(ei)){\ displaystyle O (t (n))}t{\ displaystyle t}ei{\ displaystyle n}

L=Avaruus(Hirsi⁡(ei)) .{\ displaystyle {\ mbox {L}} = {\ mbox {SPACE}} (\ log (n)) \.}

Esimerkkejä ongelmista

Esimerkkejä kielistä

Kieli on l . Tässä on algoritmi, joka päättää logaritmisessa tilassa: {0k1k∣k∈EI}{\ displaystyle \ {0 ^ {k} 1 ^ {k} \ mid k \ sisään \ mathbb {N} \}}{0k1k∣k∈EI}{\ displaystyle \ {0 ^ {k} 1 ^ {k} \ mid k \ sisään \ 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

Sana w ei ole muokattu: se on merkintä eikä sitä lasketa laskettaessa käytettyä muistia. Laskemme vain lisämuistin, nimittäin muuttujat i ja counterzero, jotka ovat positiivisia kokonaislukuja, joita rajoittaa | w | ja että voimme koodata logaritmisessa tilassa | w |

Seuraavan algebrallisen kieliopin tuottamien sanojen kieli on L: S -> (S) | SS | e.

Kertolasku

Tässä luvussa on huomioitu kokonaisluvun binaarinen esitys . Kieli on l . Seuraava algoritmi tunnistaa välilyönnin , missä on sen syötteen koko. Algoritmi ottaa syötteeksi kolme kokonaislukua n , m ja p varmistaa, että n : n kertolasku m: llä on todellakin p . Se laskee jokaisella iteraatiolla kertomisen tuloksen i - bitin ja vertaa sitä p: n i - bittiin. ei{\ displaystyle n}⟨ei⟩{\ displaystyle \ langle n \ rangle}MULT={(⟨ei⟩,⟨m⟩,⟨ei×m⟩)∣ei,m∈EI}{\ displaystyle \ mathrm {MULT} = \ vasen \ {(\ langle n \ rangle, \ langle m \ rangle, \ langle n \ kertaa m \ rangle) \ n n, m \ sisään \ mathbb {N} \ right \ }}MULT{\ displaystyle \ mathrm {MULT}}O(Hirsi⁡T){\ displaystyle {\ mathcal {O}} (\ log T)}T{\ displaystyle T}

Algoritmin kuvauksessa käytetään seuraavia menettelyjä:

• lisää ( x ), lisää muuttujaa x  ;
• est_un ( x , i ) osoittaa, jos i : nnen bitti x on ei-nolla, jos i on suurempi kuin koko x bitin katsotaan olevan nolla;
• divide_by_two ( x ), korvaa x : n sen euklidisen jaon luvulla 2; tämä voidaan toteuttaa x : n bittisiirtona yhdestä vähiten merkitsevään bittiin.

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

Käytettyjen i- , j- ja k- laskurien arvo ei ylitä merkinnän kokoa, ja se voidaan siten koodata logaritmisesti merkinnän kokoon. Esitetyt menettelyt ja vertailut käyttävät enintään yhtä logaritmista tilaa merkinnän koossa. Lopuksi valitun muuttujan arvo ei voi ylittää , joten se voidaan koodata tilaan . enint(|ei|+|m|-1,|s|)3<T3{\ displaystyle \ max \ vasen (| n | + | m | -1, | p | \ oikea) ^ {3} <T ^ {3}}O(3Hirsi⁡T){\ displaystyle {\ mathcal {O}} \ vasen (3 \ log T \ oikea)}

Suhteet muihin monimutkaisuusluokkiin

Tiedämme seuraavat sulkeumat:

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

Tiedetään myös, että L: n sisällyttäminen PSPACEen on tiukkaa, joten yksi edellä mainituista sulkeumista on tiukka. Ei ole mahdotonta, että ne kaikki ovat .

SL-luokka ja saavutettavuusongelma ohjaamattomassa kaaviossa

Lewis ja Christos Papadimitriou määrittivät vuonna 1982 L: n "symmetrisen" variantin: SL- luokan ( symmetriselle log-avaruudelle englanniksi). Alkuperäinen määritelmä käyttää symmetrisen Turing-koneen käsitettä klassisten determinististen Turing-koneiden sijaan. Vastaavasti SL on ongelmaluokka, jonka ei-deterministinen Turingin kone päättää logaritmisessa tilassa seuraavalla symmetrian rajoituksella:

• Jos kone voi siirtyä kokoonpanosta A kokoonpanoon B, kone voi myös siirtyä kokoonpanosta B kokoonpanoon A.

Siten SL- luokka on välillä L ja NL . Lewis ja Papadimitriou osoittivat, että ohjaamattoman kaavion esteettömyysongelma on SL-täydellinen ( logaritmisten pienennysten osalta ). Tämä saavutettavuusongelma ottaa syötteenä suuntaamattoman kaavion, kärkipisteen s ja kärkipisteen t ja määrittää, onko tietystä pisteestä s tietylle kärkipisteelle t polku (huomaa, että suunnattujen kuvaajien esteettömyysongelman versio on NL-täydellinen ).

Vuonna 2004 Omer Reingold osoittaa, että suuntaamattoman kuvaajan saavutettavuusongelma ratkaistaan deterministisen koneen logaritmisessa tilassa, ja siksi L = SL . Reingoldin todiste käyttää laajennuskaavioiden käsitettä . Tämä tulos ansaitsi hänelle Gödel-palkinnon vuonna 2009.

Huomautuksia ja viitteitä

1. Garey ja Johnson 1979 , s.  177 .
2. Sipser 1997 , määritelmä 8.12, s.  295 .
3. Michael Sipser , Johdatus laskentateoriaan , International Thomson Publishing,1. st joulukuu 1996, 396  Sivumäärä ( ISBN  0-534-94728-X , luettu verkossa ) , s. 349, esimerkki 8.18
4. (sisään) Dexter C. Kozen, Laskentateoria , Kotitehtävät 3. Esim. 1. s. 277
5. Michael Sipser , Johdatus laskentateoriaan , International Thomson Publishing,1. st joulukuu 1996, 396  Sivumäärä ( ISBN  0-534-94728-X , luettu verkossa ) , s. 359, esimerkki 8.20
6. Omer Reingold , Salil Vadhan ja Avi Wigderson , "  Entropy-aallot, siksak-graafinen tuote ja uudet vakioasteen laajentimet  ", Annals of Mathematics , voi.  155, n °  1,2002, s.  157–187 ( DOI  10.2307 / 3062153 , JSTOR  3062153 , Math Reviews  1888797 , lue verkossa )
7. Omer Reingold , "  Ohjaamaton yhteys lokitilassa  ", Journal of the ACM , voi.  55, n o  4,2008, s.  1–24 ( lue verkossa )

Bibliografia

• (en) Sanjeev Arora ja Boaz Barak , laskennallinen monimutkaisuus: moderni lähestymistapa , Cambridge University Press ,2009( ISBN  0-521-42426-7 ) , luku .  1 ("Laskennallinen malli - ja miksi sillä ei ole merkitystä")
• Omer Reingold , "  Ohjaamaton ST-liitettävyys log-avaruudessa  ", elektroninen kollokviumi laskennallisesta monimutkaisuudesta , n o  94,2004( lue verkossa ). Sähköinen versio.
• Omer Reingold , "  Ohjaamaton yhteys log-avaruudessa  ", Journal of the ACM , voi.  55, n o  4,2008, s.  1–24 ( DOI  10.1145 / 1391289.1391291 , matemaattiset arvostelut  2445014 ). Lehden versio.
• (en) MR Garey ja DS Johnson , Tietokoneet ja käsittelemättömyys: opas NP-täydellisyyden teoriaan , New York, WH Freeman,1979, 338  Sivumäärä ( ISBN  0-7167-1045-5 ) , osa 7.5: Logaritminen tila, s. 177–181
• (en) Christos Papadimitriou , laskennallinen monimutkaisuus , lukeminen (massa), Addison Wesley,1993, 1.  painos , 523  Sivumäärä ( ISBN  0-201-53082-1 ) , s.  Luku 16: Logaritminen tila, s. 395-408
• (en) Michael Sipser , Johdatus laskentateoriaan , PWS Publishing,1997, 396  Sivumäärä ( ISBN  0-534-94728-X ) , osa 8.4: Luokat L ja NL, s. 294–296

Ulkoiset linkit

• (en) L-luokka monimutkaisuuden eläintarhassa
• (fr) SL-luokka Complexity Zoo

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">