Derandomisierung von Polynomgleichungen

• Applicant: Professor Dr. Uwe Schöning
• Subject Area: Theoretical Computer Science
• Term: from 2004 to 2010
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants
• Participating Person: Professor Dr. Thomas Thierauf