Deterministinio laiko hierarchija
Laiko požiūriu konstruojamoms funkcijoms f,g≥n, kurioms f(n)log f(n)=o(g(n)), DTIME(f(n)) yra tikrasis DTIME(g(n)) poaibis.
Esminės žinios
Laiko požiūriu konstruojamoms funkcijoms f,g≥n, kurioms f(n)log f(n)=o(g(n)), DTIME(f(n)) yra tikrasis DTIME(g(n)) poaibis. Diagonalinis modeliavimas su įvesties papildymu duoda kalbą, kuriai reikia daugiau laiko, nei leidžia mažesnioji laiko riba. Konkrečiai, DTIME(n²)⊊DTIME(n³).
Sąlygos ir taikymo ribos
- Naudojamos įprastinės deterministinės daugiajuostės Tiuringo mašinos; DTIME(t) reiškia blogiausio atvejo O(t(n)) ribą.
- Konstruojamumas ir logaritminis modeliavimo atotrūkis yra šios teoremos dalis. Šis deterministinio laiko klasių atskyrimas neišsprendžia P ir NP santykio klausimo.
Šaltiniai · 2
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
3.4 teorema ir diagonalizacijos su įvesties papildymu įrodymas, spausdinto leidinio 3 puslapis; papildomai patvirtinančios MIT 21 paskaitos 10–11 skaidrės atskiria o(t/log t) nuo O(t).
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-time-hierarchy
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra