Derandomisierung von Polynomgleichungen

Zusammenfassung.
Viele algorithmischen (Entscheidungs-) Probleme lassen sich arithmetisieren, also in ein System von Polynomgleichungen übersetzen, so dass die Aufgabe letztlich darin besteht, eine solche (multi-variate) Polynomgleichung zu überprüfen. Dabei ist es problemabhängig oft so, dass die betreffenden Polynome nicht explizit gegeben sind, sondern nur in einer impliziten Form vorliegen, zum Beispiel als Graph, Determinate einer Matrix oder als Schaltkreis.

Eine oftmals angewandte Methode von Schwartz und Zippel besteht darin, ein randomisiertes Verfahren anzuwenden Dabei werden Zufallswerte in die (implizit gegebenen) Polynome eingesetzt und diese an den Zufallsstellen ausgewertet.

Ausgangspunkt und Motivation für dieses Projekt ist die effiziente Lösung des Primzahlproblems, welche von Agrawal, Kayal und Saxona angegeben wurde. Es stellt sich heraus, dass dieser Algorithmus als eine derandomisierte Version eines Polynomgleichungstests, wie oben beschrieben, aufgefasst werden kann. Ziel dieses Projektes ist es, die Methoden von AKS auch auf andere, ähnlich gelagerte Probleme, wie beispielsweise Perfektes Matching, oder das Äquivalenzproblem für read-once branching Programme zu übertragen.

Das Projekt hat thematische Überschneidungen mit dem vorangegangenen DFG-Projekt Die Komplexität von Problemen in der linearen Algebra.