Kétszeresen hatékony interaktív bizonyítási rendszerekről

Eredeti címe:

On Doubly-Efficient Interactive Proof Systems

Könyv tartalma:

Egy interaktív bizonyítási rendszert akkor nevezünk kétszeresen hatékony rendszernek, ha az előírt bizonyító stratégia polinomiális időben, a hitelesítő stratégiája pedig közel lineáris időben valósítható meg. Az ilyen bizonyítási rendszerek az interaktív bizonyítási rendszer előnyeit elérhetővé teszik a valós életben a polinomiális idejű számításokra korlátozott ágensek számára.

Az On Doubly-Efficient Interactive Proof Systems áttekint néhány ismert eredményt a duplán hatékony interaktív bizonyítási rendszerekkel kapcsolatban. Két egyszerű t-no-CLIQUE konstrukció bemutatásával kezdi, ahol az első konstrukció előnye, hogy általánosítható bármely „lokálisan jellemezhető” halmazra, a második konstrukció előnye pedig, hogy megőrzi a probléma kombinatorikus ízét. Ezután rátér a kétszeresen hatékony interaktív bizonyítási rendszer két általánosabb konstrukciójára: a (egyenletes) korlátos mélységű körökkel rendelkező halmazok bizonyítási rendszerére és a polinomidőben és kis térben felismerhető halmazok bizonyítási rendszerére.

A GKR-konstrukció bemutatása teljes, és némileg eltér az eredeti bemutatótól. Rövid áttekintést adunk az RRR-konstrukcióról.