O podwójnie wydajnych interaktywnych systemach dowodzenia

Oryginalny tytuł:

On Doubly-Efficient Interactive Proof Systems

Zawartość książki:

Interaktywny system dowodzenia jest nazywany podwójnie wydajnym, jeśli zalecana strategia dowodzącego może być zaimplementowana w czasie wielomianowym, a strategia weryfikatora może być zaimplementowana w czasie prawie liniowym. Takie systemy dowodowe sprawiają, że korzyści płynące z interaktywnego systemu dowodowego są dostępne dla rzeczywistych agentów, którzy są ograniczeni do obliczeń w czasie wielomianowym.

W artykule On Doubly-Efficient Interactive Proof Systems dokonano przeglądu niektórych znanych wyników dotyczących podwójnie wydajnych interaktywnych systemów dowodzenia. Zaczyna się od przedstawienia dwóch prostych konstrukcji dla t-no-CLIQUE, gdzie pierwsza konstrukcja oferuje korzyść w postaci uogólnienia na dowolny „lokalnie charakteryzowalny” zbiór, a druga konstrukcja oferuje korzyść w postaci zachowania kombinatorycznego charakteru problemu. Następnie omówiono dwie bardziej ogólne konstrukcje podwójnie wydajnych interaktywnych systemów dowodzenia: system dowodzenia dla zbiorów posiadających (jednolite) obwody o ograniczonej głębokości oraz system dowodzenia dla zbiorów rozpoznawanych w czasie wielomianowym i w małej przestrzeni.

Prezentacja konstrukcji GKR jest kompletna i różni się nieco od oryginalnej prezentacji. Przedstawiono krótki przegląd konstrukcji RRR.