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

Uniforme Charakterisierungen von Komplexitätsklassen

Es werden verschiedene Komplexitätsklassen mit Hilfe von einheitlichen Berechnungsmodellen charakterisiert. Auf diese Weise soll von speziellen Eigenschaften der (ursprünglichen) Definitionen der Klassen abstrahiert werden und eine uniforme Untersuchung verschiedener Klassen ermöglicht werden. Ein erfolgreiches Beispiel für dieses Vorgehen ist die Trennung der Klassen TC0 (der Probleme, die von Booleschen Schaltkreisen in konstanter Tiefe und polynomieller Größe mit Schwellwertgatter gelöst werden können) und PP (der Probleme, die sich von probabilistischen Turingmaschinen in polynomieller Zeit lösen lassen).

Blattsprachen-Homepage

Ausgewählte Publikationen