Logaritminės ir polinominės atminties klasės
DSPACE(s(n)) ir NSPACE(s(n)) apima sprendimo uždavinių kalbas, kurias deterministinės ir nedeterministinės Tiuringo mašinos atpažįsta naudodamos O(s(n)) darbinės atminties.
Esminės žinios
DSPACE(s(n)) ir NSPACE(s(n)) apima sprendžiamąsias kalbas, kurias deterministinės ir nedeterministinės Tiuringo mašinos gali atpažinti naudodamos O(s(n)) darbinės atminties. L=DSPACE(log n), NL=NSPACE(log n), PSPACE=⋃ₖ≥₁DSPACE(nᵏ), o NPSPACE=⋃ₖ≥₁NSPACE(nᵏ).
Sąlygos ir taikymo ribos
- Subtiesinėms riboms naudojama atskira tik skaitoma įvesties juosta, neįskaičiuojama į darbinę atmintį, ir fiksuota baigtinė juostos abėcėlė; n yra užkoduotos įvesties ilgis.
- Sprendžiančiosios mašinos sustoja su kiekviena įvestimi, o nedeterministinių mašinų atveju – kiekvienoje skaičiavimo šakoje; įvestis priimama, jei yra bent viena ją priimanti šaka. Darbinę atmintį galima naudoti pakartotinai, todėl maža atminties riba savaime nereiškia panašios laiko ribos.
Šaltiniai · 2
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Massachusetts Institute of Technology2 šaltiniai
Pagrindimas ir peržiūra
Paskaitos 20 skaidrėje 2 pateiktos tik skaitomos įvesties ir darbinės juostos apibrėžtys; paskaitos 17 skaidrėje 2 pateiktos sustojančių deterministinių ir nedeterministinių mašinų atminties bei PSPACE apibrėžtys. Polinominės atminties apibrėžtys sutampa nepriklausomai nuo to, ar įvesties langeliai įskaičiuojami.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-space-complexity-classes
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra