Interactive and probabilistically checkable proofs in real number models
Final Report Abstract
Hauptgegenstand der Untersuchungen war die Frage nach der 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 wurden verschiedene Szenarien betrachtet. Im Mittelpunkt des Projekts standen sogenannte probabilistisch prüfbare Beweise. Bei diesen überprüft der Verifizierer einen ihm vorgelegten potentiellen Beweis einer Aussage auf Richtigkeit. Eine wesentliche Frage ist jetzt, für welche Klassen von Aussagen dies dem Verifizierer mit welchen Ressourcen gelingt. Eines der zentralen Ergebnisse der theoretischen Informatik in den letzten zwei Dekaden ist der sogenannte PCP-Satz. Er besagt, dass NP-vollständige Probleme im Turingmodell randomisiert verifiziert werden künnen. Dabei erzeugt der Verifizierer eine logarithmische Anzahl von Zufallsbits und prüft anschliessend lediglich konstant viele Stellen des vorgelegten Beweises, um mit hoher Wahrscheinlichkeit richtig zu entscheiden. Im Projekt wurde dieser Satz fiir das Rechenmodell von Blum, Shub und Smale uüber sowohl den reellen wie den komplexen Zahlen untersucht und schlussendlich auch bewiesen. Ein typisches NP-vollständiges Problem über diesen Strukturen ist das Hilbert-Nullstellensatz-Problem. Dabei wird gefragt, ob ein vorgelegtes polynomiales Gleichungssystem über dem entsprechenden Körper eine Lösung besitzt. Die Projektergebnisse zeigen, dass es möglich ist, für die (potentielle) Lösbarkeit eines vorgelegten Systems einen (potentiellen) Beweis anzugeben, der randomisiert nur in konstant vielen Stellen zu prüfen ist, um mit hoher Wahrscheinlichkeit zu schlussfolgern, ob er korrekt ist. Es konnte im Wesentlichen gezeigt werden, dass sich dieser neue PCP-Satz wie auch die diskrete klassische Variante sowohl mit graphentheoretischen als auch mit algebraischen Methoden beweisen lässt. Dabei war es allerdings nötig, die bekannten Beweistechniken deutlich zu erweitern, um den Problemen Rechnung zu tragen, die durch Betrachtung überabzählbarer Strukturen entstehen. Die Ergebnisse implizieren ebenfalls, dass es (unter Standardvoraussetzungen der Komplexitätstheorie) nicht möglich ist, die maximale Anzahl von gemeinsam lösbaren Gleichungen eines Polynomsystems effizient zu approximieren. Beim oben erwähnten zweiten Szenario, den interaktiven Beweisen, tauscht der Verifizierer mit einem beliebig machtvollen sogenannten Beweiser gemäß eines Kommunikationsprotokolls Informationen aus. Am Ende dieses Prozesses trifft der Verifizierer wiederum seine Entscheidung, ob er von der Richtigkeit des Beweises überzeugt ist. Hier wurden im letzten Teil des Projekts erste Ergebnisse zur Mächtigkeit dieser interaktiven Protokolle im reellen Rechenmodell erzielt. Dazu gehören der Nachweis einer oberen Schranke für Probleme, die derart behandelt werden können sowie der Entwurf solcher Protokolle für konkrete Problemklassen.
Publications
- Almost transparent short proof for N PR . Extended abstract in: Proc. 18th International Symposium on Fundamentals of Computation Theory FCT 2011, Oslo, Lecture Notes in Computer Science 6914, 41–52, 2011
K. Meer
- The PCP theorem for NP over the reals. Extended abstract in: Proc. 30th Symposium on Theoretical Aspects of Computer Science STACS 2013, Leibniz International Proceedings in Informatics (LIPIcs) series vol. 20, Schloss Dagstuhl, 104-115, 2013
M. Baartse, und K. Meer
- Topics in real and complex number complexity theory. In: Recent Advances in Real Complexity and Computation, Contemporary Mathematics vol. 604, J.L. Montana, L.M. Pardo (Hrg.), American Mathematical Society, 1–53, 2013
M. Baartse und K. Meer
- Testing low degree trigonometric polynomials. Extended Abstract in: Proc. 9th International Computer Science Symposium in Russia CSR 2014, Moscow, N.K. Vereshchagin, E.A. Hirsch, S.O. Kuznetsov, J.E. Pin (eds.), Springer LNCS 8476, 77–96, 2014
M. Baartse und K. Meer
(See online at https://doi.org/10.1007/978-3-319-06686-8_7) - Some results on interactive proofs for real computations. In: Beckmann A., Mitrana V., Soskova M. (eds) Evolving Computability. CiE 2015, pp 107-116 . Lecture Notes in Computer Science, vol 9136. Springer, Cham
M. Baartse und K. Meer
(See online at https://doi.org/10.1007/978-3-319-20028-6_11) - The PCP theorem for NP over the reals. Foundations of Computational Mathematics, June 2015, Volume 15, Issue 3, pp 651–680
M. Baartse, und K. Meer
(See online at https://doi.org/10.1007/s10208-014-9188-x) - An algebraic proof of the real number PCP theorem. Journal of Complexity, Volume 40, June 2017, Pages 34-77. Part of special issue:
Dedicated to the memory of Joseph F. Traub, Part II
M. Baartse und K. Meer
(See online at https://doi.org/10.1016/j.jco.2016.11.006)
