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.^[1]

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^[2]. Die Autoren erhielten dafür den ersten Gödel-Preis 1993.

1. ↑ Fourer et al. On Completeness and Soundness in Interactive Proof Systems On Completeness and Soundness in Interactive Proof Systems Advances in Computing Research 1989
2. ↑ Babai, Moran: Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes, Journal of Computer and System Sciences, Band 36, 1988, Seite 254–276