Vorlesung Schaltkreiskomplexität (WS 2009/10)

Vorlesung aus dem Master-Kernmodul Komplexitätstheorie (10-202-2112)

Organisatorisches


Inhalt

Schaltkreise stellen ein formales Modell für parallele Rechner dar. In der Komplexitätstheorie werden sie deshalb zur Definition "paralleler Komplexitätsklassen" verwendet. Die Tiefe eines Schaltkreises (= maximale Länge eines Pfades von einem Eingangsgatter zu einem Ausgangsgatter) entspricht dabei der auf einer parallelen Maschine benötigten Zeit. In der Vorlesung sollen zunächst Schaltkreise für arithmetische Operationen (Addition, Multiplikation, Division) behandelt werden. Ein Großteil der Vorlesung behandelt untere Schranken für Schaltkreise. Es soll dabei gezeigt werden, dass sich gewisse Operationen nicht mit Resourcen-beschränkten Schaltkreisen berechnen lassen. Hierbei werden insbesondere algebraische Techniken (endliche Körper) benutzt. Schließlich sollen noch Beziehungen zwischen Schaltkreiskomplexität und Logik behandelt werden.

Folien (Version vom 05.02.2010)


Lehrbücher


Impressum
Last modified: Thu Oct 2 19:10:17 CEST 2003