Deterministinės atminties hierarchija
Jei S yra atminties požiūriu konstruojama funkcija, S(n)≥n ir s(n)=o(S(n)), tai DSPACE(s(n))⊊DSPACE(S(n)).
Esminės žinios
Jei S yra atminties požiūriu konstruojama funkcija, S(n)≥n ir s(n)=o(S(n)), tai DSPACE(s(n))⊊DSPACE(S(n)). Pavyzdžiui, DSPACE(n)⊊DSPACE(n²): pakankamai didesnė konstruojama darbinės atminties riba leidžia atpažinti naujas sprendimo kalbas.
Sąlygos ir taikymo ribos
- Šioje formuluotėje naudojama šaltinyje pateikta didesnioji ≥n riba, tik skaityti skirta įvestis ir darbinės atminties klasės.
- Išvada yra klases atskiriančios kalbos egzistavimas, o ne teiginys, kad kiekvienam algoritmui naudinga papildoma atmintis ar kad iš to išplaukia P≠PSPACE.
Šaltiniai · 2
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Skaidrių 6 puslapyje 4 pateiktas atminties hierarchijos teiginys, o puslapiuose 5–6 – konstravimo susitarimai; MIT paskaitos 21 skaidrėse 8–9 pateikti diagonalizacija grindžiamo įrodymo su atminties apribojimu metmenys.
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-deterministic-space-hierarchy
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra