Interaktives Beweissystem
Sign in to savein computational complexity theory, an abstract machine modeling computation as two parties (an untrusted but powerful ‘prover’; a trusted ‘verifier’ with bounded resources) exchanging messages to ascertain whether some string belongs to a language
Article · Deutsch
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.
Abstract from DBpedia / Wikipedia · CC BY-SA