Interaktyvūs įrodymai ir kvantoriais apibrėžtas pagrįstumas
Tyrimų kontekstas
postgraduate concept · established · Patikros data 2026-10-10
Interaktyvus įrodymas leidžia polinominiu laiku veikiančiam atsitiktinumą naudojančiam tikrintojui keistis pranešimais su skaičiavimo ištekliais neapribotu įrodinėtoju.
Esminės žinios
Interaktyvus įrodymas leidžia polinominiu laiku veikiančiam atsitiktinumą naudojančiam tikrintojui keistis pranešimais su skaičiavimo ištekliais neapribotu įrodinėtoju. Pilnumas užtikrina sėkmingą sąžiningą įrodinėtoją teigiamuose uždavinio egzemplioriuose; pagrįstumas riboja priėmimo tikimybę kiekvienam sukčiaujančiam įrodinėtojui neigiamuose egzemplioriuose. Kartojimas ir tikimybinių garantijų stiprinimas turi išlaikyti protokolo modelį. Tuo tarpu argumentas riboja tik skaičiavimo ištekliais apribotus sukčiaujančius įrodinėtojus, todėl būtina nurodyti jo skaičiavimo sunkumo prielaidas ir išteklių ribas.
Sąlygos ir taikymo ribos
- Nurodykite kalbą arba įvesties aprėpties pažadą (promise), pranešimų skaičių bei ilgį, tikrintojo naudojamą atsitiktinumą ir pilnumo bei pagrįstumo tikimybes.
- Patikrintas sąžiningos sąveikos išrašas neįrodo visiems sukčiaujantiems įrodinėtojams taikomos pagrįstumo sąlygos.
Šaltiniai · 2
Š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: IP apibrėžimas, grafų neizomorfiškumas ir tikrintojo atsitiktinumas; šifravimo žaidimai, skyriai 2–3/9/12, autentifikavimas, skyriai 6–8, parašai, skyrius 13, redukcijos ir tapatybės nustatymas bei nulinis žinojimas, skyriai 18–20. 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-interactive-proof-completeness
- Versija
- research.1
- Struktūruotas žinyno įrašas
- Podiplominis ir tyrimų žinynas