Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
  • Zielgruppen
  • Suche
 

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

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.

Ausgewählte Veröffentlichungen