Interaktiver Beweis für HORN-SAT?

Gibt es eine Möglichkeit, wie ein Prüfer einen Prüfer davon überzeugen kann, dass ein HORN-SAT-Ausdruck zufriedenstellend ist?

Dies mag natürlich albern erscheinen, da es für HORN-SAT lineare Zeitalgorithmen gibt. Andererseits ist HORN-SAT P-vollständig, was bedeutet, dass es keine Log-Space-Algorithmen gibt, es sei denn, P = L. Beschränken Sie dementsprechend die Rechenfähigkeiten des Verifizierers auf L. Jetzt ist der Verifizierer sehr schwach, sodass das Problem nicht länger albern ist.

Eine weitere Wendung ist, ob es sich um einen wissensfreien Beweis handeln kann.

cc.complexity-theory interactive-proofs zero-knowledge Shaun Harker
quelle

Im Fall von Nicht-Null-Wissen denke ich, dass die naive Überprüfung unter Verwendung einer zufriedenstellenden Wahrheitszuweisung als Zertifikat nur Protokollspeicherplatz erfordert, vorausgesetzt, die Eingabe und das Zertifikat sind auf schreibgeschützten Bändern geschrieben, die nicht als Speicherplatz gelten.

Tsuyoshi Ito

@ Tsuyoshi: Ich sehe nicht, wie man eine naive Überprüfung nur im Protokollbereich durchführt. Wenn wir könnten, würde das nicht zeigen, dass HORN-SAT in NL ist und somit nach P-Vollständigkeit P = NL ergibt?

Shaun Harker

Nein. Ich habe angenommen, dass sich das Zertifikat auf einem schreibgeschützten Band befindet, was sich von der von NL durchgeführten Überprüfung unterscheidet.

Tsuyoshi Ito

@ Tsuyoshi: Ah, Sie können das Zertifikat also viele Male lesen, während eine zertifikatbasierte Definition von NL ein Zertifikat haben würde, das nur einmal gelesen werden kann.

Shaun Harker

Antworten:

Diese http://www.cs.ubc.ca/~condon/papers/ips-survey.pdf Umfrage von Anne Condon enthält viele Fakten über raumgebundene interaktive Proofsysteme.

Es gibt mehrere Modelle, und die Hauptunterschiede bestehen darin, ob Sie private Münzen für den Prüfer (IP) oder nur öffentliche Münzen (AM) zulassen und ob Sie die Überprüfungszeit auch auf Polynome beschränken (nicht impliziert durch den allein gebundenen Raum).

Ohne zeitliche Beschränkung lautet die Antwort ja: IP (Log-Space) enthält EXP und AM (Log-Space) = P.

Beachten Sie, dass IP (Log-Space) höchstwahrscheinlich größer als Standard-IP ist. Andererseits ist IP (Log-Space, Poly-Time) = IP = PSPACE.

AM (log-space, poly-time) = P aufgrund von 'Delegating Computation: Interactive Proofs for Muggles' von Goldwasser et al., STOC 2008.

Darüber hinaus zeigt das Papier 'Zero Knowledge with Log-Space-Verifizierer' von Kilian (FOCS 88), wie man ein Log-Space-Poly-Time-Zero-Knowledge-Proof-System für alles in IP erhält (natürlich mit privaten Münzen).

Hartmut Klauck
quelle

Ich habe auch ein Papier mit dem Titel Delegating Computation: Interactive Proofs for Muggles gefunden . Zeigt Satz 3 dieser Arbeit, dass AM (log-space, poly-time) = P ist?

Shaun Harker

Ja, das zeigen sie tatsächlich!

Hartmut Klauck