Derandomisierung von Polynomgleichungen

• Antragsteller: Professor Dr. Uwe Schöning
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2004 bis 2010
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5423284

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, Determinante einer Matrix oder als Schaltkreis. Eine oftmals angewandte Methode besteht darin, ein randomisiertes Verfahren anzuwenden. Dabei werden Zufallswerte in die (implizit gegebenen) Polynome eingesetzt und diese an den Zufallsstellen ausgewertet (Sch80, Zip79]. Ausgangspunkt und Motivation für dieses Projekt ist die effiziente Lösung des Primzahlproblems, welche von Agrawal, Kayal und Saxona [AKS02] 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.

• DFG-Verfahren: Sachbeihilfen
• Beteiligte Person: Professor Dr. Thomas Thierauf