L (kompleksitet) - L (complexity)

I beregningskompleksitetsteori er L (også kjent som LSPACE eller DLOGSPACE ) kompleksitetsklassen som inneholder beslutningsproblemer som kan løses av en deterministisk Turing -maskin ved hjelp av en logaritmisk mengde skrivbart minneplass . Formelt har Turing -maskinen to bånd, hvorav den ene koder inngangen og bare kan leses, mens den andre båndet har logaritmisk størrelse, men kan leses så vel som skrevet. Logaritmisk plass er tilstrekkelig til å holde et konstant antall pekere i inngangen og et logaritmisk antall boolske flagg, og mange grunnleggende loggromsalgoritmer bruker minnet på denne måten.

Fullstendige problemer og logisk karakterisering

Hver ikke-triviell problem i L er fullført i henhold til log-reduksjoner plass , er så svake reduksjon er nødvendig for å identifisere meningsfulle forestillinger om L -completeness, og det vanligste er første-ordens reduksjoner .

Et resultat fra 2004 av Omer Reingold viser at USTCON , problemet med om det eksisterer en bane mellom to hjørner i en gitt ikke -dirigert graf , er i L , som viser at L = SL , siden USTCON er SL -komplett.

En konsekvens av dette er en enkel logisk karakterisering av L : den inneholder nettopp de språkene som kan uttrykkes i første ordens logikk med en ekstra kommutativ transitiv lukkeoperator (i grafteoretiske termer gjør dette hver tilkoblede komponent til en klikk ). Dette resultatet kan også anvendes for databasen spørrespråk : data kompleksiteten av en spørring er definert som kompleksiteten i å besvare et fast spørring med tanke på datastørrelsen som den variable inngangs. For dette tiltaket, spørringer mot relasjonsdatabaser med komplett informasjon (som ikke har oppfatningen av nullpunkt ) slik det for eksempel i relasjons algebra er i L .

Relaterte kompleksitetsklasser

L er en underklasse av NL , som er klassen av språk som kan velges i logaritmisk plass på en ikke -deterministisk Turing -maskin . Et problem i NL kan omdannes til et problem med tilgjengelighet i en rettet graf som representerer tilstander og tilstandsoverganger til den ikke -deterministiske maskinen, og det logaritmiske rombundet innebærer at denne grafen har et polynomisk antall hjørner og kanter, hvorfra det følger at NL er inneholdt i kompleksitetsklassen P av problemer som kan løses i deterministisk polynomtid. Således L  ⊆  NL  ⊆  P . Inkluderingen av L i P kan også bevises mer direkte: en avgjørelse som bruker O (log  n ) plass kan ikke bruke mer enn 2 ^{O (log  n )}  =  n ^{O (1)} tid, fordi dette er det totale antallet mulige konfigurasjoner.

L angår videre klasse NC på følgende måte: NC ¹  ⊆  L  ⊆  NL  ⊆  NC ² . Med ord gitt en parallell datamaskin C med et polynomtall O ( n ^k ) for prosessorer for noen konstante k , kan ethvert problem som kan løses på C i O (log  n ) tid i L , og ethvert problem i L kan være løst i O (log ²  n ) på tidspunktet C .

Viktige åpne problemer inkluderer om L  =  P , og om L  =  NL . Det er ikke engang kjent om L  =  NP .

Den relaterte klassen av funksjonsproblemer er FL . FL brukes ofte til å definere logromsreduksjoner .

Ytterligere eiendommer

L er lav for seg selv, fordi den kan simulere log-space-orakel-spørringer (grovt sett "funksjonsanrop som bruker loggplass") i loggplass, og gjenbruke samme plass for hver spørring.

Andre bruksområder

Hovedideen med logrom er at man kan lagre et polynomstørrelse i logrommet og bruke det til å huske pekere til en posisjon av inngangen.

Logrom -klassen er derfor nyttig for å modellere beregning der inngangen er for stor til å passe inn i RAM -en til en datamaskin. Lange DNA -sekvenser og databaser er gode eksempler på problemer der bare en konstant del av inngangen vil være i RAM på et gitt tidspunkt, og hvor vi har tips for å beregne den neste delen av inngangen for å inspisere, og dermed bare bruke logaritmisk minne.

Se også

• L/poly , en ikke-enhetlig variant av L som fanger kompleksiteten til forgreningsprogrammer i polynomstørrelse

Merknader

Referanser

• Arora, Sanjeev ; Barak, Boaz (2009). Beregningskompleksitet. En moderne tilnærming . Cambridge University Press . ISBN 978-0-521-42426-4. Zbl  1193.68112 .
• Papadimitriou, Christos (1993). Computational Complexity (1. utg.). Addison Wesley. Kapittel 16: Logaritmisk rom, s. 395–408. ISBN 0-201-53082-1.
• Sipser, Michael (1997). Introduksjon til beregningsteorien . PWS Publishing. Del 8.4: Klassene L og NL, s. 294–296. ISBN 0-534-94728-X.
• Garey, MR ; Johnson, DS (1979). Datamaskiner og uoverkommelighet: En guide til teorien om NP-fullstendighet . WH Freeman. Avsnitt 7.5: Logaritmisk rom, s. 177–181 . ISBN 0-7167-1045-5.
• Cook, Stephen A .; McKenzie, Pierre (1987). "Problemer fullført for deterministisk logaritmisk rom" (PDF) . Journal of Algorithms . 8 (3): 385–394. doi : 10.1016/0196-6774 (87) 90018-6 . ISSN  0196-6774 .