NL uždarumas papildinio atžvilgiu
NL=coNL: nedeterministine logaritmine atmintimi sprendžiamų kalbų papildiniai taip pat priklauso NL.
Esminės žinios
NL=coNL: nedeterministine logaritmine atmintimi sprendžiamų kalbų papildiniai taip pat priklauso NL. Pasiekiamumu grindžiamame įrodyme patvirtinamas pasiekiamų viršūnių skaičius, todėl nepasiekiamumą galima tikrinti naudojant nedeterministinę logaritminę darbinę atmintį.
Sąlygos ir taikymo ribos
- Papildinys imamas visų baigtinių eilučių, sudarytų iš nurodytos įvesties abėcėlės simbolių, aibės atžvilgiu.
- Nepakanka sukeisti kiekvienos nedeterministinės Tiuringo mašinos (NTM) šakos priėmimo ir atmetimo rezultatų: priėmimo sąlygoje šakoms taikomas egzistavimo kvantorius. Iš šios teoremos neišplaukia NP=coNP.
Šaltiniai · 2
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Massachusetts Institute of Technology2 šaltiniai
Pagrindimas ir peržiūra
Paskaitos 20 skaidrės 9–12, Immermano–Szelepcsényi teorema ir pasiekiamumo konstrukcija, grindžiama skaičiavimu; užbaigiama paskaitos 21 skaidrėse 2–6.
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-nondeterministic-space-complement
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra