Arithmetische und Boole'sche Komplexität

In diesem Projekt werden Beziehungen zwischen der arithmetischen und der Boole'schen Komplexität untersucht: 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 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.