Savičiaus deterministinis modeliavimas pagal atmintį
Jei s(n)≥log n yra pagal atmintį konstruojama funkcija, tai NSPACE(s(n))⊆DSPACE(s(n)²).
Esminės žinios
Jei s(n)≥log n yra pagal atmintį konstruojama funkcija, tai NSPACE(s(n))⊆DSPACE(s(n)²). Rekursinis pasiekiamumo tikrinimas skaičiavimo konfigūracijų grafe kiekviename lygyje saugo vieną vidurio konfigūraciją: kiekvienam iš O(s(n)) lygių reikia O(s(n)) darbinės atminties. Todėl PSPACE=NPSPACE ir NL⊆DSPACE(log²n).
Sąlygos ir taikymo ribos
- Taikyti atminties sudėtingumo klasių įraše aprašytą tik skaitomos įvesties ir darbinės atminties konvenciją bei sprendžiančiąsias mašinas.
- Modeliavimo rėžis yra atminties rėžio kvadratas; juo neteigiama, kad L=NL ar P=NP arba kad kiekvieną polinominės atminties skaičiavimą galima modeliuoti per polinominį laiką.
Šaltiniai · 3
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Massachusetts Institute of Technology2 šaltiniai
- CS6810 (Spring 2026 posting), Lecture 8: Space complexity and logspaceEshan Chattopadhyay / Cornell UniversityPaskaitų medžiaga · PDF
Pagrindimas ir peržiūra
Paskaitos 18 skaidrėje 4 pateikta teorema ir įrodymas, grindžiamas vidurio konfigūracija bei konfigūracijų skaičiumi, kai rėžiai ≥n; paskaitos 20 skaidrėje 4 tiesiogiai patikrinamas logaritminės atminties atvejis. Kornelio universiteto paskaitos 8 spausdintame puslapyje 1 pateikta bendroji forma pagal atmintį konstruojamam rėžiui ≥log n.
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-savitch-space-simulation
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra