On Doubly-Efficient Interactive Proof Systems
Interaktívny dôkazový systém sa nazýva dvojnásobne efektívny, ak predpísanú stratégiu overovateľa možno implementovať v polynomiálnom čase a stratégiu overovateľa možno implementovať v takmer lineárnom čase. Takéto dôkazové systémy sprístupňujú výhody interaktívneho dôkazového systému reálnym agentom, ktorí sú obmedzení na výpočty v polynomiálnom čase.
V práci On Doubly-Efficient Interactive Proof Systems sú uvedené niektoré známe výsledky týkajúce sa dvojnásobne efektívnych interaktívnych dôkazových systémov. Začína predstavením dvoch jednoduchých konštrukcií pre t-no-CLIQUE, kde prvá konštrukcia ponúka výhodu zovšeobecnenia na akúkoľvek „lokálne charakterizovateľnú“ množinu a druhá konštrukcia ponúka výhodu zachovania kombinatorického charakteru problému. Potom sa venuje dvom všeobecnejším konštrukciám dvojnásobne efektívneho interaktívneho dôkazového systému: dôkazovému systému pre množiny, ktoré majú (rovnomerné) obvody s ohraničenou hĺbkou, a dôkazovému systému pre množiny, ktoré sú rozpoznateľné v polynomiálnom čase a malom priestore.
Prezentácia konštrukcie GKR je úplná a trochu sa líši od pôvodnej prezentácie. Stručný prehľad je uvedený pre konštrukciu RRR.
