IP=PSPACE ir polinomų suderinamumo patikros
Tyrimų kontekstas
postgraduate concept · established · Patikros data 2026-10-10
Lygybė IP=PSPACE taikoma polinominiu laiku atliekamam atsitiktiniam tikrinimui, kai sąveikų skaičius polinominis, o įrodinėtojas neapribotas.
Esminės žinios
Lygybė IP=PSPACE taikoma polinominiu laiku atliekamam atsitiktiniam tikrinimui, kai sąveikų skaičius polinominis, o įrodinėtojas neapribotas. Aritmetizavimas paverčia Bulio skaičiavimą teiginiais apie mažo laipsnio polinomus, tikrinamais atsitiktiniuose lauko taškuose; laipsnio ribos ir lauko dydis valdo pagrįstumo klaidą. Atvirkštinė įtrauktis imituoja sąveiką naudodama polinominę atmintį. Ši teorema taikoma tiksliai apibrėžtam įrodymo modeliui, o ne trumpiems deterministiniams kiekvieno PSPACE teiginio įrodymams.
Sąlygos ir taikymo ribos
- Konstrukcija apima tikrintojo išteklius, baigtinio lauko pateikimą, polinomo laipsnį ir leistiną klaidos ribą.
- Polinominiu laiku veikiantis tikrintojas gali sąveikauti per polinominį pranešimų skaičių; pašalinus sąveiką modelis pasikeičia.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Autorius patikrino šį anglišką teiginį, pateiktą lygtį, jei ji yra, ir nurodytas prielaidas pagal šias šaltinių vietas: aritmetizavimas, polinomų suderinamumo patikros ir PSPACE imitavimas. Patikra apsiriboja užrašytais teiginiais; neteigiama, kad visiškai atkurtas įrodymas, pakartotinai atlikta programinė įrodymo patikra ar aprėpta visa literatūra.
2026-10-10 · Autoriaus atlikta šaltinio teksto, teiginio, lygties ir taikymo srities patikra; grafo sąsajų aprėptis nurodyta atskirai. Prieš užbaigiant šaką būtina atskira nepriklausoma turinio, šaltinių ir inventoriaus peržiūra.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- research-info-ip-pspace-arithmetization
- Versija
- research.1
- Struktūruotas žinyno įrašas
- Podiplominis ir tyrimų žinynas