Untersuchungen Arithmetischer und Boole'scher Komplexität von Schaltkreisen kleiner Tiefe

• Antragsteller: Professor Dr. Heribert Vollmer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2015 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 270077289

Die Komplexitätstheorie wird bestimmt von der Suche nach effizienten Algorithmen (obere Schranken) sowie nach Beweisen, dass Algorithmen bestimmter Komplexität nicht existieren (untere Schranken). Arithmetische Schaltkreise haben sich in den vergangenen Jahren zu einem populären Berechnungsmodell entwickelt, da sie einerseits eine sehr natürliche Formulierung (insbesondere numerischer) Algorithmen erlauben, aber andererseits aufgrund ihrer restriktiven Struktur zu einer Reihe beeindruckender unterer Schranken führten. In den achtziger und neunziger Jahren des vergangenen Jahrhunderts war die Untersuchung Boole'scher Schaltkreise sehr verbreitet wegen des Aufkommens tiefliegender Techniken zur Erzielung unterer Schranken.Ziel des hier beantragten Projekts ist eine systematische Erforschung der Beziehungen zwischen arithmetischen und Boole'schen Schaltkreisen, um offene Fragen in beiden Berechnungsmodellen zu untersuchen. Die angestrebten Ergebnisse sollen unser Verständnis der Struktur kleiner Komplexitätsklassen innerhalb der Klasse P aller effizient lösbaren Probleme verbessern.

• DFG-Verfahren: Sachbeihilfen