Kvantifikuotų Bulio formulių teisingumas ir PSPACE-pilnumas
TQBF uždavinys klausia, ar visiškai kvantifikuota baigtinė Bulio formulė yra teisinga.
Esminės žinios
TQBF uždavinys klausia, ar visiškai kvantifikuota baigtinė Bulio formulė yra teisinga. Egzistencinių kvantorių šakos jungiamos operacija ARBA, o visuotinių kvantorių – operacija IR; vertinant paieška į gylį, daugianario dydžio darbinė atmintis naudojama pakartotinai. TQBF yra PSPACE-pilnas pagal daugianario laiko daugelio į vieną redukcijas.
Sąlygos ir taikymo ribos
- Kiekvienas kintamasis yra susietas kvantoriumi; formulės ilgis lemia įvesties dydį.
- Vertinimas gali užtrukti eksponentinį laiką, nors naudojama daugianario dydžio atmintis. PSPACE-sunkumui įrodyti naudojamos kvantifikuotos pasiekiamumo konstrukcijos, o ne tiesioginė eksponentinio dydžio skaičiavimo lentelė.
Š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 17 skaidrėse 5–6 pateiktas rekursinis vertinimas ir jo gylio ryšys su atminties sąnaudomis; paskaitos 18 skaidrėse 5–9 pateikti pilnumo apibrėžimas ir teorema bei kvantifikuota vidurinio taško konstrukcija (daugianario dydžio bendri parinkimo kintamieji).
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-quantified-boolean-pspace
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra