Konstruojamos išteklių ribos
Laiko riba t(n)≥n čia vadinama konstruojama laiko atžvilgiu, jei Tiuringo mašina, gavusi unarinę įvestį 1ⁿ, gali per O(t(n)) laiko užrašyti 1ᵗ⁽ⁿ⁾.
Esminės žinios
Laiko riba t(n)≥n čia vadinama konstruojama laiko atžvilgiu, jei Tiuringo mašina, gavusi unarinę įvestį 1ⁿ, gali per O(t(n)) laiko užrašyti 1ᵗ⁽ⁿ⁾. Atminties riba s(n)≥log n čia vadinama konstruojama atminties atžvilgiu, jei jos vertę galima apskaičiuoti iš 1ⁿ naudojant O(s(n)) darbinės atminties. Šios prielaidos leidžia simuliacijai užtikrinti, kad nebūtų viršytas jos išteklių biudžetas.
Sąlygos ir taikymo ribos
- Ribų vertės yra teigiami sveikieji skaičiai; logaritmų apvalinimas ir baigtinio skaičiaus mažų n reikšmių nepaisymas šių asimptotinių klasių nekeičia.
- Tai nurodyti konstravimo susitarimai, o ne teiginys, kad kiekvieną apskaičiuojamą funkciją galima apskaičiuoti naudojant jos pačios vertės neviršijantį išteklių biudžetą.
Šaltiniai · 2
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Kornelio universiteto paskaitos 3 apibrėžtis 3.1, spausdintas puslapis 3; Oksfordo universiteto skaidrės 6, puslapiai 5–6, konstravimo atminties atžvilgiu apibrėžtis ir biudžeto skaitiklis. Įprastos polinominės ribos, tokios kaip n²,n³, atitinka šiuos ribotų išteklių konstravimo susitarimus.
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-constructible-resource-bounds
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra