Puncte:2

Care este semnificația verificatorului este „ppt”? și de ce avem nevoie de verificatorul este ppt în Interactive Proof?

drapel nl

Am studiat Zero Knowledge Proof. Am găsit că Definiția Interactive Proof spune că Verifier este ppt. Și am găsit doar în PP (Complexitate) Wikipedia spune ca ppt:

Mașinile Turing care sunt legate polinomial și probabilistice sunt caracterizat ca PPT, care reprezintă timp polinomial probabilist mașini.[2] Această caracterizare a mașinilor Turing nu necesită o probabilitate de eroare mărginită. Prin urmare, PP este clasa de complexitate conţinând toate problemele rezolvabile prin a PPT mașină cu o eroare probabilitate mai mică de 1/2.

Încă este foarte confuz despre PPT, care este numele complet al PPT? avem nevoie ca verificatorul să fie PPT pentru Proof interactiv?

Resursă de la: Zero Knowledge Proofs CS276: Criptografie, UC Berkeley

Puncte:2
drapel et

PPT este algoritmul de timp polinomial probabilist.

Un verificator determinist va produce întotdeauna aceeași ieșire/răspuns pentru orice intrare.

Să luăm o secvență interactivă.

Prover trimite $p_1$.

Verificatorul răspunde cu $f(p_1) = v_1$

Prover răspunde cu $g(v_1) = p_2$

Functia $f$ pe care o folosește verificatorul este deterministă. adică pentru o anumită intrare, acesta răspunde întotdeauna cu același răspuns.

Într-un verificator probabilist, $f$ are, de asemenea, randomizare ca intrare. adică $g$ are 2 intrări $f(v_i, r)$ Unde $r$ este o valoare aleatorie. Prin urmare $f$ nu este determinist, iar verificatorul este un verificator probabilist. Si daca $f$ rulează în timp polinomial, verificatorul este un verificator Probabilistic Polynomial Time (PPT).

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.