Laiko ir atminties klasių įtrauktys bei eksponentinis laikas
L⊆NL⊆P⊆NP⊆PSPACE=NPSPACE⊆EXP, kur EXP=⋃ₖ≥₁DTIME(2ⁿᵏ).
Esminės žinios
L⊆NL⊆P⊆NP⊆PSPACE=NPSPACE⊆EXP, kur EXP=⋃ₖ≥₁DTIME(2ⁿᵏ). Sustojanti mašina, naudojanti polinominį atminties kiekį, turi tik eksponentinį konfigūracijų skaičių; logaritminę atmintį naudojančios mašinos konfigūracijų grafas yra polinominio dydžio. Pagal deterministinę laiko hierarchiją P⊊EXP.
Sąlygos ir taikymo ribos
- Visos klasės apima užkoduotus baigtinius sprendimo uždavinius ir remiasi tuo pačiu įprastu mašinos modeliu.
- Šios įtrauktys nereiškia, kad kiekviena gretimų klasių įtrauktis yra griežta. Griežtos P ir EXP įtraukties rezultatui galima naudoti diagonalizacija apibrėžtą kalbą su konstruojama 2ⁿ laiko riba, nepatenkančią į jokią polinominę laiko ribą.
Šaltiniai · 3
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Massachusetts Institute of Technology2 šaltiniai
- Computational Complexity (2023), Slides 6: Space hierarchy and constructibilityPaul W. Goldberg / University of OxfordPaskaitų medžiaga · PDF
Pagrindimas ir peržiūra
Paskaitos 17 skaidrėse 3–4 pateiktas konfigūracijų skaičiavimas pagal laiko ir atminties ribas bei NP⊆PSPACE; paskaitos 20 skaidrėse 3–5 – L/NL⊆P; Oksfordo skaidrių 6 puslapiuose 2–3 aptariama EXP ir griežta įtrauktis P⊊EXP, grindžiama laiko hierarchija.
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-complexity-class-inclusions
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra