Despre sistemele de demonstrație interactive dublu eficiente

Titlul original:

On Doubly-Efficient Interactive Proof Systems

Conținutul cărții:

Un sistem de demonstrație interactiv este numit dublu eficient dacă strategia prescrisă pentru prover poate fi implementată în timp polinomial, iar strategia verificatorului poate fi implementată în timp aproape liniar. Astfel de sisteme de dovezi pun beneficiile sistemelor interactive de dovezi la dispoziția agenților din viața reală care sunt limitați la calculul în timp polinomial.

Studiul On Doubly-Efficient Interactive Proof Systems trece în revistă unele dintre rezultatele cunoscute referitoare la sistemele de dovezi interactive dublu eficiente. Începe prin prezentarea a două construcții simple pentru t-no-CLIQUE, în care prima construcție oferă avantajul generalizării la orice set „local caracterizabil”, iar a doua construcție oferă avantajul păstrării caracterului combinatorial al problemei. Se trece apoi la două construcții mai generale ale sistemului de dovezi interactive dublu eficiente: sistemul de dovezi pentru seturi care au circuite (uniforme) cu adâncime limitată și sistemul de dovezi pentru seturi care sunt recunoscute în timp polinomial și spațiu mic.

Prezentarea construcției GKR este completă și este oarecum diferită de prezentarea originală. Se oferă o scurtă prezentare generală a construcției RRR.