Interaktywny dowód dla HORN-SAT?

Czy istnieje sposób, w jaki przysłowie może przekonać weryfikatora, że niektóre wyrażenia HORN-SAT są zadowalające?

Oczywiście może się to wydawać głupie, ponieważ istnieją algorytmy czasu liniowego dla HORN-SAT. Z drugiej strony HORN-SAT jest P-zupełny, co oznacza, że nie ma algorytmów przestrzeni logów, chyba że P = L. W związku z tym ogranicz możliwości obliczeniowe weryfikatora do L. Teraz weryfikator jest bardzo słaby, więc problem nie jest już głupi.

Kolejnym zwrotem jest to, czy może to być dowód braku wiedzy.

cc.complexity-theory interactive-proofs zero-knowledge Shaun Harker
źródło

W przypadku niezerowej wiedzy uważam, że naiwna weryfikacja przy użyciu zadowalającego przypisania prawdy jako certyfikatu wymaga tylko miejsca w dzienniku, pod warunkiem, że dane wejściowe i certyfikat są zapisane na taśmach tylko do odczytu, które nie liczą się jako spacja.

Tsuyoshi Ito,

@Tsuyoshi: Nie widzę, jak dokonywać naiwnej weryfikacji tylko w przestrzeni dziennika. Jeśli moglibyśmy, czyż nie pokazałoby to, że HORN-SAT jest w NL, a zatem przez P-kompletność daje P = NL?

Shaun Harker

Nie. Zakładam, że certyfikat znajduje się na taśmie tylko do odczytu, co różni się od weryfikacji przeprowadzanej przez NL.

Tsuyoshi Ito

@Tsuyoshi: Ach, więc możesz czytać certyfikat wiele razy, podczas gdy oparta na certyfikatach definicja NL miałaby certyfikat, który można odczytać tylko raz.

Shaun Harker,

Odpowiedzi:

Ta http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf ankieta przeprowadzona przez Anne Condon zawiera wiele faktów na temat interaktywnych systemów dowodzenia ograniczonych przestrzenią.

Istnieje kilka modeli, a główne różnice dotyczą tego, czy zezwalasz na prywatne monety weryfikatora (IP), czy tylko monety publiczne (AM) i czy ograniczasz również czas weryfikacji do wielomianu (nie wynika to z samej spacji).

Bez ograniczenia czasowego odpowiedź brzmi tak: IP (log-space) zawiera EXP i AM (log-space) = P.

Zauważ, że IP (przestrzeń logów) jest najprawdopodobniej większy niż standardowe IP. Z drugiej strony IP (log-space, poly-time) = IP = PSPACE.

AM (log-space, poly-time) = P z powodu 'Delegating Computation: Interactive Proofs for Muggles' autorstwa Goldwasser i in., STOC 2008.

Ponadto artykuł „Zerowa wiedza z weryfikatorami przestrzeni logów” autorstwa Kiliana (FOCS 88) pokazuje, jak uzyskać system sprawdzania wiedzy w czasie wielomiejscowym zerowej wiedzy dla wszystkiego w IP (oczywiście z prywatnymi monetami).

Hartmut Klauck
źródło

Znalazłem także artykuł zatytułowany Delegowanie obliczeń: interaktywne dowody dla mugoli . Czy Twierdzenie 3 tej pracy pokazuje, że AM (log-space, poly-time) = P?

Shaun Harker

Tak, rzeczywiście to pokazują!

Hartmut Klauck