Circuit Complexity

Bei der Circuit Complexity werden als Berechnungsmodell Schaltkreise betrachtet. Dadurch ergeben sich andere Maße für den Ressourcenbedarf als in der klassischen Komplexitätstheorie. Wir interessieren uns besonders für den Zusammenhang von gewissen Schaltkreisklassen, Logikklassen erster Stufe und Algebra.

Schaltkreise werden als gerichtete, azyklische Graphen modelliert, wobei die Gatter mit boolschen Funktionen beschriftet sind. Ein Schaltkreis hat eine feste Zahl von Eingaben und Ausgaben. Um also Sprachen erkennen zu können, muss man dazu übergehen, Familien von Schaltkreisen zu betrachten. Bei Schaltkreisen werden als Ressourcen typischerweise die Anzahl der Gatter, die Tiefe und die verwendeten Gattertypen betrachtet.