Stand: 14. September 1998

»Konkrete Komplexitätstheorie«

Vorlesung im WS 98/99

Vorlesungsplan

Vorlesung (V4) 
Di  9 - 11      E2.304
Übung (Ü1) 
Do  9 - 11      D2.343           letztes Mal: 11.2. 9:00 st


Dozent:

Friedhelm Meyer auf der Heide
Raum:   F1.301
Tel.:   60 64 80
Fax:   60 64 82
EMail:  fmadh@uni-paderborn.de

 
Übungsgruppenleiter:

Martin Ziegler
Raum:   F1.119
Tel.:   (05251) 60 64 27
Fax:   (05251) 60 64 82
EMail:  ziegler@uni-paderborn.de



Kurzbeschreibung der Vorlesung

Die Komplexitätstheorie versucht, Probleme bezüglich des Aufwandes zu klassifizieren, der notwendig ist, um sie auf einem Rechner zu lösen. Aufwand wird dabei z.B. durch Laufzeit oder Speicherplatzbedarf gemessen. Während die strukturelle Komplexitätstheorie versucht, Probleme verschiedenen Komplexitätsklassen zuzuordnen, und z.B. mit Hilfe von Reduktionen Probleme bezüglich ihrer Komplexität zu vergleichen, sucht die Konkrete Komplexitätstheorie explizite Komplexitätsschranken für Probleme in vorgegebenen Rechenmodellen. (In Info C wird z.B. gezeigt: Jeder vergleichsbasierte Sortieralgorithmus benötigt mindestens n log(n) Vergleiche.)
In dieser Vorlesung werden für verschiedene sequentielle und parallele Rechenmodelle Methoden zum Beweis mehrerer Schranken vorgestellt. Unter anderem werden Rechenmodelle wie Schaltkreise, Turingmaschinen, Registermaschinen und Berechnungsbäume mit verschiedenen Operationsmengen sowie parallele Rechenmodelle untersucht.




Themenübersicht


Teil 1: Schaltkreise
  1. Einführung
  2. Beispiel: Schaltkreise für die Addition
  3. Obere und untere Schranken für die Schaltkreiskomplexität fast aller Boole'scher Funktionen
  4. Schaltkreise versus Turingmaschinen
  5. Eine untere Schranke für monotone Schaltkreise
  6. Eine untere Schranke für Schaltkreise mit beschränkter Tiefe
Teil 2: Algebraische Berechnungen und Registermaschinen
  1. Einführung
  2. Simulationen zwischen Registermaschinen und Berechnungsbämen
  3. Berechenbarkeitsbegriff für verschiedene Operationsmengen
  4. Die Component Counting Lower Bound
  5. Untere Schranken für Registermaschinen
  6. Effiziente Berechnungsbäme
Teil 3: Parallele Registermaschinen (PRAMs)
  1. Einfürung
  2. Exakte Laufzeitschranken für CREW-PRAMs




Übungsblätter




Nützliche Parallelveranstaltung



(vorläufige) Literaturliste

  • Ingo Wegener: "The Complexity of Boolean Functions" Wiley-Teuber 1987, 41TVM2013
  • Peter Bürgisser, Michael Clausen, M. Amin Shokrollahi: "Algebraic Complexity Theory", Springer 1997, 41TEK1116
  • Uri Zwick: "Boolean Circuit Complexity", Lecture Notes
  • Rüdiger Reischuk: "Einführung in die Komplexitätstheorie", Teubner 1990, 41TVM2437
  • David Dobkin, Richard J. Lipton: "A Lower Bound of n2/2 on Linear Search Programs for the Knapsack Problem", Journal of Computer and System Sciences 16, 413-417 (1978)
  • Katharina Lürwer-Brüggemeier, Friedhelm Meyer auf der Heide: "Capabilities and Complexity of Computations with Integer Division", Proc. of the 10th STACS 463-472 (1993)
  • M. Ben Or: "Lower bounds for Algebraic Computation Trees", Proceedings of the 15the ACM STOC 80-86 (1983), 60TTQ830773
Bemerkung: Die beiden Lehrbücher sind sehr viel umfangreicher als die Vorlesung. Wir werden nur einige, meist anders aufbereitete Ergebnisse besprechen.