Tobias Berg: Komplexität inverser Probleme

Der Projektionssatz für NP-Sprachen besagt, dass man sich eine NP-Berechnung in zwei Phasen unterteilt vorstellen kann: eine nichtdeterministische Ratephase und eine deterministische Prüfphase. Die in der ersten Phase geratenen Wörter nennen wir Zertifikate. Das Prädikat, welches die geratenen Wörter in der zweiten Phase dann überprüft, nennen wir Verifier.

Das Problem, zu einer gegebenen Eingabe (Sprechweise: Theorem) einen Beweis zu finden, ist schon vielfältig untersucht worden. Das inverse Problem besteht nun darin, zu einer gegebenen Menge von Zertifikaten, ein Theorem zu finden, welches genau diese Zertifikate besitzt.

Im Rahmen des Vortrages werden wir das inverse Problem auch für andere Klassen als NP betrachten, so z.B die Klassen der Polynomialzeithierarchie und die Klasse RE. Ausserdem werden wir auf verschiedene Repräsentationsmöglichkeiten der Liste von Zertifikaten (also der Eingabe für das inverse Problem) eingehen.