Tikimybiškai tikrinami įrodymai ir užklausos į atskiras jų vietas
Tyrimų kontekstas
postgraduate concept · established · Patikros data 2026-10-10
PCP teorema išreiškia NP=PCP(O(log n),O(1)): polinominiu laiku veikiantis tikrintojas naudoja logaritminį atsitiktinių bitų skaičių ir užklausia pastovų vietų skaičių polinominio ilgio įrodyme; pilnumas lygus vienetui, o klaidingo priėmimo tikimybė apribota, pavyzdžiui, viena antrąja.
Esminės žinios
PCP teorema išreiškia NP=PCP(O(log n),O(1)): polinominiu laiku veikiantis tikrintojas naudoja logaritminį atsitiktinių bitų skaičių ir užklausia pastovų vietų skaičių polinominio ilgio įrodyme; pilnumas lygus vienetui, o klaidingo priėmimo tikimybė apribota, pavyzdžiui, viena antrąja. Tiesioginė prieiga prie pasirinktos įrodymo vietos yra modelio dalis. Tai nėra teiginys, kad bet kokį užrašytą įrodymą galima patikimai patikrinti perskaičius kelis sakinius ir jo neužkodavus.
Sąlygos ir taikymo ribos
- Aiškiai nurodomi įvesties ilgis n, prieiga prie įrodymo orakulo, uniformus tikrintojas ir pilnumo bei pagrįstumo susitarimai.
- Praktiniam tikrinimui svarbūs įrodymo ilgis, kodavimo konstrukcija ir paslėptos konstantos.
Š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: NP=PCP(O(log n),O(1)), pilnumas bei pagrįstumas ir įrodymo orakulo modelis. 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-pcp-oracle-model
- Versija
- research.1
- Struktūruotas žinyno įrašas
- Podiplominis ir tyrimų žinynas