Logaritminės atminties redukcijos ir orientuotasis pasiekiamumas
Logaritminės atminties daugelio į vieną redukcija apskaičiuoja f taip, kad x∈A tada ir tik tada, kai f(x)∈B, naudodama tik skaitomą įvestį, O(log n) darbinę juostą ir tik rašomą išvestį.
Esminės žinios
Logaritminės atminties daugelio į vieną redukcija apskaičiuoja f taip, kad x∈A tada ir tik tada, kai f(x)∈B, naudodama tik skaitomą įvestį, O(log n) darbinę juostą ir tik rašomą išvestį. Pasiekiamumo iš s į t orientuotajame grafe uždavinys yra NL-pilnas šių redukcijų atžvilgiu: apriboto ilgio keliui nedeterministiškai atspėti pakanka logaritminės atminties, o kiekvienas NL skaičiavimas redukuojamas į jo polinominio dydžio konfigūracijų grafą.
Sąlygos ir taikymo ribos
- Redukcija sustoja su kiekviena įvestimi; jos išvestis neprivalo tilpti darbinėje juostoje, o jos ilgis yra polinominis.
- Komponuojant redukcijas arba imituojant B, reikiamus išvesties simbolius reikia generuoti iš naujo, o ne saugoti visą tarpinę išvestį. Grafo viršūnės ir briaunos turi aiškiai apibrėžtą baigtinį kodavimą.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 20 skaidrės 6–8: keitiklio ir redukcijos apibrėžtys, simbolių generavimo iš naujo argumentas ir PATH pilnumo įrodymas.
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-logspace-reductions-reachability
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra