Interaktives Beweissystem

Ein interaktives Beweissystem ist ein Begriff aus der Komplexitätstheorie. Dabei wird eine abstrakte Maschine, in welcher die Informationsverarbeitung durch den Austausch von Nachrichten realisiert ist, beschrieben. Ein interaktives Beweissystem muss die Completeness und Soundnessbedingung erfüllen.

Sie wurden 1985 von Shafi Goldwasser, Charles Rackoff und Silvio Micali eingeführt (wobei Preprints bis auf 1982 zurückgingen) und unabhängig von László Babai 1985, der darüber später ausführlich mit Shlomo Moran veröffentlichte. Die Autoren erhielten dafür den ersten Gödel-Preis 1993.

↑ Fourer et al.: On Completeness and Soundness in Interactive Proof Systems. (PDF; 155 kB) In: Advances in Computing Research. 1989, archiviert vom Original am 27. November 2015; abgerufen am 27. August 2008 (englisch).
↑ László Babai, Shlomo Moran: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. In: Journal of Computer and System Sciences, Band 36, Nr. 2. 1988, S. 254–276, abgerufen am 24. August 2010 (englisch).

[Fourer-1] Fourer et al.: On Completeness and Soundness in Interactive Proof Systems. (PDF; 155 kB) In: Advances in Computing Research. 1989, archiviert vom Original am 27. November 2015; abgerufen am 27. August 2008 (englisch).

[2] László Babai, Shlomo Moran: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. In: Journal of Computer and System Sciences, Band 36, Nr. 2. 1988, S. 254–276, abgerufen am 24. August 2010 (englisch).