Thema der
Vorlesung ist die Berechnung boolescher Funktionen durch
kombinatorische Schaltkreise. Ein Schaltkreis ist ein gerichteter
azyklischer Graph, in dessen Knoten (Gatter) boolesche Operationen
(z.B. Und, Oder, Nicht) ausgewertet werden. Wir werden Schaltkreise
für grundlegende Funktionen (Addition, Multiplikation, Sortieren
usw.) konstruieren. Dabei wird sich neben der Größe (Anzahl
der benutzten Gatter) auch die Schaltkreistiefe (maximale
Pfadlänge) als ein aussagekräftiges
Komplexitätsmaß erweisen. Schaltkreisfamilien bilden ein
wichtiges Berechnungsmodell für parallele
Komplexitätsklassen. Analog zur NP-Vollständigkeit wurde eine
Theorie der P-Vollständigkeit entwickelt, um nicht
parallelisierbare Probleme identifizieren zu können.
Empfohlene
Literatur
H. Vollmer, Introduction to Circuit Complexity, Springer Verlag, 1999.