O dvojnásobně efektivních interaktivních důkazových systémech

Původní název:

On Doubly-Efficient Interactive Proof Systems

Obsah knihy:

Interaktivní důkazový systém se nazývá dvojnásobně efektivní, pokud lze předepsanou strategii proveru implementovat v polynomiálním čase a strategii verifikátoru lze implementovat v téměř lineárním čase. Takové důkazové systémy zpřístupňují výhody interaktivního důkazového systému agentům v reálném životě, kteří jsou omezeni na výpočty v polynomiálním čase.

V článku On Doubly-Efficient Interactive Proof Systems jsou uvedeny některé známé výsledky týkající se dvojnásobně efektivních interaktivních důkazových systémů. Začíná představením dvou jednoduchých konstrukcí pro t-no-CLIQUE, kde první konstrukce nabízí výhodu zobecnění na libovolnou „lokálně charakterizovatelnou“ množinu a druhá konstrukce nabízí výhodu zachování kombinatorického charakteru problému. Poté se věnuje dvěma obecnějším konstrukcím dvojnásobně efektivního interaktivního důkazového systému: důkazovému systému pro množiny, které mají (rovnoměrné) obvody s omezenou hloubkou, a důkazovému systému pro množiny, které jsou rozpoznatelné v polynomiálním čase a malém prostoru.

Prezentace konstrukce GKR je úplná a poněkud se liší od původní prezentace. Pro konstrukci RRR je uveden stručný přehled.