Interaktive und probabilistisch prüfbare Beweise in reellen Rechenmodellen

• Antragsteller: Professor Dr. Klaus Meer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2011 bis 2014
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 195586166

Das Vorhaben untersucht die Stärke interaktiver und probabilistisch prüfbarer Beweise im Rahmen von Rechenmodellen, die auf überabzählbaren Strukturen wie den reellen Zahlen arbeiten. Bei derartigen Beweisen soll sich ein mit gewissen Ressourcen ausgestatteter randomisierter Algorithmus, der sogenannte Verifizierer, von der Richtigkeit einer mathematischen Aussage überzeugen. Dabei werden verschiedene Szenarien betrachtet. Bei interaktiven Beweisen tauscht der Verifizierer mit einem bzgl. seiner Ressourcen beliebig machtvollen Algorithmus, dem Beweiser, gemäß eines Kommunikationsprotokolls Informationen aus. Am Ende dieses Prozesses trifft der Verifizierer eine Entscheidung, ob er durch die gelieferten Informationen des Beweiers von der Richtigkeit des Beweises der Aussage überzeugt ist oder nicht. Bei probabilistisch prüfbaren Beweisen findet keine Kommunikation statt, der Verifizierer überprüft stattdessen einen ihm vorgelegten potentiellen Beweis einer Aussage auf Richtigkeit. Im Mittelpunkt der Untersuchungen steht die Frage, für welche Klassen von Aussagen dies Verifizierern mit welchen Ressourcen gelingt. Hauptziel des Projekts ist es, auf diese Art verschiedene zentrale reellle Komplexitätsklassen zu charakterisieren, und damit das Verständnis über letztere auszudehnen und zu vertiefen. Des weiteren soll der Zusammenhang solcher Charakterisierungen mit der Existenz von effizienten Näherungsverfahren für schwierige Probleme analysiert werden. Dies ist bei der praktischen Behandlung schwieriger Probleme von Bedeutung.

• DFG-Verfahren: Sachbeihilfen