000259661 001__ 259661
000259661 005__ 20240928175343.0
000259661 0247_ $$aG:(GEPRIS)416961355$$d416961355
000259661 035__ $$aG:(GEPRIS)416961355
000259661 040__ $$aGEPRIS$$chttp://gepris.its.kfa-juelich.de
000259661 150__ $$aTest von Polynomgleichungen und algebraische Komplexität$$y2019 -
000259661 371__ $$aProfessor Dr. Thomas Thierauf
000259661 450__ $$aDFG project G:(GEPRIS)416961355$$wd$$y2019 -
000259661 5101_ $$0I:(DE-588b)2007744-0$$aDeutsche Forschungsgemeinschaft$$bDFG
000259661 680__ $$aDas Problem Polynom Identitätstest (PIT) -- entscheide, ob ein Polynom gegeben als arithmetischer Schaltkreis das Nullpolynom ist -- spielt eine zentrale Rolle in der arithmetischen Schaltkreis Komplexitätstheorie. PIT wird in vielen fundamentalen Resultaten der Komplexitätstheorie benützt, wie zum Beispiel Primzahltest, das PCP-Theorem und vielen anderen Problemen, die als Polynomgleichungen formuliert werden können. Es gibt effiziente randomisierte Algorithmen für PIT und eine der größten Herausforderungen in der Komplexitätstheorie ist es effiziente deterministische Algorithmen für das Problem zu finden. Eine allgemeine Derandomisierung von randomisierten Komplexitätsklassen wird als ein sehr schwieriges Problem angesehen, da man weiß, dass daraus starke untere Schranken für Schaltkreise folgen. Auf der anderen Seite gibt es Resultate wie den berühmten AKS-Primzahltest der zeigt, dass Derandomisierung für spezifische Probleme mit gewissen algebraischen Strukturen möglich ist. Ein prominenter Kandidat ist das perfekte Matching Problem (für parallele Algorithmen) und Verallgemeinerungen zu Matroiden. Das Ziel des Projekts ist es Derandomisierungen von weiteren, allgemeineren Strukturen zu bekommen. Durch die Verbindung zu PIT sind untere Schranken für arithmetische Berechnungsmodelle im Fokus, wie zum Beispiel arithmetische Schaltkreise, branching Prgramme oder Formeln. Dies motiviert auch Abgeschlossenheitseigenschaften der jeweiligen Komplexitätsklassen zu betrachten.
000259661 909CO $$ooai:juser.fz-juelich.de:926264$$pauthority$$pauthority:GRANT
000259661 909CO $$ooai:juser.fz-juelich.de:926264
000259661 980__ $$aG
000259661 980__ $$aAUTHORITY