Vikipedio:Projekto matematiko/L (komplekseco)
El Vikipedio
 |
Ĉi tiu artikolo montras stilajn aŭ/kaj gramatikajn aŭ/kaj strukturajn problemojn kaj bezonas poluradon por konformi al pli bona nivelo de kvalito. Post plibonigo movu la artikolon al L (komplekseco) (eble la nomo mem bezonas korekton) Se la ligo estas ruĝa, vi povas movi la artikolon. Se la ligo estas blua, la alia artikolo pri la temo jam ekzistas kaj tiun kaj ĉi tiun artikolon necasas kunigi. |
En komputa komplekseca teorio, L estas la komplekseca klasa enhavanta decido (problemoj, problemas) kiu povas esti solvita per (determinisma, determina) Maŝino de Turing uzanta logaritma kvanto de memora spaco. Intuicie, logaritma spaco estas sufiĉa spaco al teni konstanta nombro de (nadloj, nadlas) enen la (enigo, enigi) kaj logaritma nombro de bulea (flagoj, flagas, kaheloj, kahelas, standardoj, standardas).
Ĝeneraligo de L estas Nl, kiu estas la klaso de lingvoj decidebla en logaritma spaco sur _nondeterministic_ Maŝino de Turing. Ni tiam bagatele havi 
. Ankaŭ, finala uzanta O(logo n) spaco ne povas uzi pli ol 2O(logo n)=nO(1) tempo, ĉar ĉi tiu estas la tuteca nombro de ebla (konfigur(aĵ)oj, konfiguroj, konfiguras); tial, 
, kie P estas la klaso de (problemoj, problemas) solvebla en (determinisma, determina) polinoma tempo.
Ĉiu problemo en L estas plenumi sub logo-spaco (rabatoj, rabatas, malpligrandiĝoj, malpligrandiĝas); ekde ĉi tiu estas sentaŭga, (pli lama, pli malforta) (rabatoj, rabatas, malpligrandiĝoj, malpligrandiĝas) estas difinita kiu permesi identigo de pli forta plenumi (problemoj, problemas) en L, sed estas ne ĝenerale akceptis difino de L-plenumi.
Grava (malfermi, malfermita) (problemoj, problemas) inkluzivi ĉu L = P, kaj ĉu L = Nl.
La rilatanta klaso de funkciaj problemoj estas _FL_. _FL_ estas ofte kutima difini _logspace_ (rabatoj, rabatas, malpligrandiĝoj, malpligrandiĝas).
Breĉa Oktobro 2004 papero per _Omer_ _Reingold_ montris (tiu, ke, kiu) _USTCON_, la problemo de ĉu tie ekzistas vojo inter du verticoj en donita sendirekta grafeo, estas en L, (fundamentanta, establanta, konstruanta, fondanta) (tiu, ke, kiu) L = Sl, ekde _USTCON_ estas Sl-plenumi.
Unu konsekvenco de ĉi tiu estas simpla logika karakterizado de L: ĝi enhavas precize tiuj lingvoj esprimebla en unua (mendi, ordo) logiko kun adiciis komuta transitiva fermaĵa operatoro (en (grafikaĵo, grafeo) teoria (termoj, kondiĉoj, terminoj, termas, terminas), ĉi tiu (kurbiĝoj, kurbiĝas, turnas, tornas, kurbigas) ĉiu koneksa komponanto enen kliko).
L estas malalta por sin, ĉar ĝi povas simuli logo-spaca orakolo (demandoj, demandas) (malglate parolanta, "funkcio (vokas, vokoj) kiu uzi loga spaco") en loga spaco, reuzanta la sama spaco por ĉiu (informmendo (serĉomendo ktp), demando).
[redaktu] Referencoj
- Ĉapitro 16: Logaritma spaco, _pp_.395–408.
- Nedirektita St-konekteco en Logo-Spaco. _Omer_ _Reingold_. Elektronika Kolokvo sur Komputa Komplekseco. Ne. 94.
- Sekcio 8.4: La Klasoj L kaj Nl, _pp_.294–296.
- Sekcio 7.5: Logaritma Spaco, _pp_.177–181.
