Derandomisierung von Polynomgleichungen
Zusammenfassung der Projektergebnisse
Die Komplexität des eindeutigen perfekten Matching Problems und des polynomiell beschränkten perfekten Matching Problems wurden stark verbessert. Offen bleibt das allgemeine perfekte Matching Problem. Der randomisierte NC2-Algorithmus ist die derzeit beste bekannte obere Schranke. Unser Ansatz beim polynomiell beschränkten perfekten Matching Problem derandomisiert diesen Algorithmus. Wir denken, dass sich dieser Ansatz auch auf das allgemeine Problem erweitern lässt. Ein Beweis dafür wäre eine echter Durchbruch und ist Thema zukünftiger Projekte. Die Ergebnisse für Algorithmen auf Quanten-Rechner zeigen die Möglichkeiten und Grenzen dieses Rechner am Beispiel mehrerer algebraischer Problemstellungen. Dabei wurde insbesondere die Determinante betrachtet, da sie beim perfekten Matching Problem eine wichtige Rolle spielt. Die Ergebnisse zum Graph Isomorphie Problem für planere Graphen stellen einen großen Fortschritt gegenüber den bisher bekannten Algorithmen dar. Zusätzlich wird das Problem genau charakterisiert, es ist vollständig für logarithmischen Platz, L. Über eine der Arbeiten wurde in der Tagespresse [Schwäbische Post vom 12.12.08] berichtet. Eine Kopie des Artikels ist in der Anlage. Die klassischen Ergebnisse von Routh und Hurwitz über die Anzahl der Nullstellen von Polynomen in der komplexen Halbebene führten zu den Resultaten über die Inertia einer Matrix. Entscheidend dabei ist, dass der Satz von Routh und Hurwitz diese Anzahlen mit Hilfe von Determinanten aus der Routh-Hurwitz-Matrix berechnet. Dadurch konnten wir die Komplexität der Berechnung der Inertia einer Matrix exakt klassifizieron, nämlich in der Komplexitätsklasse PL.
Projektbezogene Publikationen (Auswahl)
- On Closure Properties of GapL. Technical Report, ECCC Report TR04-24, 2004
T.M. Hoang und T. Thierauf
- On the Minimal Polynomial of a Matrix. International Journal of Foundations of Computer Science 15(1), 89-105, 2004
T.M. Hoang und T . Thierauf
- The Complexity of the Inertia and some Closure Properties of GapL. 20th Computational Complexity Conference (CCC), IEEE Computer Society, 28-37, 2005
T.M. Hoang und T . Thierauf
- On the unique perfect matching problem. 33rd International Colloquium on Automata, Languages and Programming (ICALP), Springer-Verlag, LNCS 4052, 453- 464, 2006
T.M. Hoang, Meena Mahajan und T. Thierauf
- The Polynomially Bounded Perfect Matching Problem is in NC2. Technical Report, ECCC Report TR06-129, 2006
Manindra Agrawal, T.M. Hoang und T. Thierauf
- The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace. Technical Report, ECCC Report TR07-068, 2007
Thomas Thierauf und Fabian Wagner
- The Polynomially Bounded Perfect Matching Problem is in NC2. 24th Symposium on Theoretical Aspects of Computer Science (STACS), Springer Verlag, LNCS 4349, 489-499, 2007
Manindra Agrawal, T.M. Hoang und T . Thierauf
- The quantum query complexity of algebraic properties. In Proceedings of the 16th International Symposium on Fundamentals of Computation Theory (FCT), Springer-Verlag, LNCS 4639, 250-260, 2007
S. Dörn und T. Thierauf
- A Log-space Algorithm for Canonization of Planar Graphs. Technical Report, 2008
Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf und Fabian Wagner
- The isomorphism problem for planar 3-connected graphs is in unambigous logspace. In (electronic) Proceedings of 25th Symposium on Theoretical Aspects of Computer Science (STACS), , 633-644, 2008
T . Thierauf und F. Wagner
- The quantum complexity of of group testing. In Proceedings of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). Springer-Verlag, LNCS 4910, 506-518, 2008
S. Dörn und T. Thierauf
