Boolescher Schaltkreis

In der theoretischen Informatik (insbesondere in der Komplexitätstheorie) ist ein boolescher Schaltkreis ein mathematisches Modell für digitale Schaltungen.

Formale Definitionen

Gatter

Gatter sind die Bestandteile, aus denen boolesche Schaltkreise aufgebaut sind. Diese bekommen boolesche Eingaben und kombinieren diese zu einem booleschen Wert als Ausgabe. Es gibt verschiedene Typen von Gattern, die Eingaben unterschiedlich kombinieren. Ein Gatter-Typ ist eine boolesche Funktion, die ein k-Tupel von booleschen Werten auf einen booleschen Wert abbildet.

Beispiele für Gatter-Typen:

Die Familie von AND-Gattern: Für jede beliebige Stelligkeit k gibt es ein $\wedge _{k}$ -Gatter, das genau dann 1 ausgibt, wenn alle Eingaben 1 sind. Für $k=2$ notieren wir die Gatter auch mit $\wedge$ , d. h., $\wedge =\wedge _{2}$
Die Familie von OR-Gattern: Für jede beliebige Stelligkeit k gibt es ein $\vee _{k}$ -Gatter, das genau dann 1 ausgibt, wenn mindestens eine Eingabe 1 ist. Für $k=2$ notieren wir die Gatter auch mit $\vee$ , d. h., $\vee =\vee _{2}$
Das Negations-Gatter $\neg$ : Es hat genau eine Eingabe und gibt 1 aus genau dann, wenn die Eingabe 0 ist.

Boolescher Schaltkreis

Ein $n$ -Input- $m$ -Output-boolescher-Schaltkreis über eine Basis $\Upsilon$ von Gattertypen ist ein gerichteter azyklischer Graph $G=(V,E)$ . Die Knoten des Graphen werden auch als Gatter bezeichnet.

Es gibt $n$ Knoten $i_{1},i_{2},\dots ,i_{n}\in V$ , die Inputs, die keine eingehenden Kanten haben.
Die verbleiben Knoten werden als interne Knoten bezeichnet.
Jedem internen Knoten ist ein Gattertyp $\upsilon \in \Upsilon$ zugeordnet, dessen Stelligkeit mit dem In-Grad des Knoten übereinstimmt (wenn notwendig, wird auch die Reihenfolge der eingehenden Kanten festgelegt).
Des Weiteren gibt es $m$ Knoten $o_{1},o_{2},\dots ,o_{m}$ , die als Output-Knoten markiert sind.

Eine häufige Wahl für die Basis $\Upsilon$ ist $\Upsilon =\{\wedge ,\vee ,\neg \}$ (manchmal auch als Standardbasis bezeichnet), da mit diesen Gatter-Typen alle Booleschen Funktionen gebildet werden können.

Funktion des Schaltkreises

Für eine Eingabe $X=(x_{1},x_{2},\dots ,x_{n})$ wird jedem Knoten $v\in V$ des Schaltkreises $C$ wie folgt ein Wahrheitswert $g_{v}(X)\in \{0,1\}$ zugewiesen:

Jeder Input-Knoten $i_{j}$ bekommt den Wert $x_{j}$ , d. h. $g_{i_{j}}(X)=x_{j}$ .
Interne Knoten werden so ausgewertet, dass zuerst alle Vorgänger ausgewertet werden, bevor der Knoten selbst ausgewertet wird und diese Werte dann entsprechend dem Gatter-Typ kombiniert werden.

Für einen internen Knoten

v\in V

mit

k

direkten Vorgängern

u_{1},\dots u_{k}

und Gatter-Typ

\upsilon \in \Upsilon

berechnet man

g_{v}(X)

als

g_{v}(X)=\upsilon (g_{u_{1}}(X),\dots ,g_{u_{k}}(X))

Die boolesche Funktion $f_{C}(X)$ eines booleschen Schaltkreises $C$ ist dann

f_{C}(X)=(g_{o_{1}}(X),\dots ,g_{o_{m}}(X))

.

Begriffe

Der Subschaltkreis eines internen Knotens $v$ besteht aus allen Gattern, die Vorgänger von $v$ sind, d. h., von denen es einen gerichteten Pfad zu $v$ gibt.
Der Grad einer Basis $\Upsilon$ ist die maximale Stelligkeit ihrer Elemente.
Monotoner Schaltkreis: Ein boolescher Schaltkreis $C$ , bei dem die Funktion $f_{C}(\cdot )$ monoton in dem Sinne ist, dass, wann immer $X=(x_{1},\dots ,x_{n}),Y=(y_{1},\dots ,y_{n}),x_{j}\leq y_{j}$ für $1\leq j\leq n$ , auch $f_{C}(X)_{j}\leq f_{C}(Y)_{j}$ für $1\leq j\leq m$ gilt. Oft werden damit auch boolesche Schaltkreise, die nur aus AND und OR Gattern bestehen, bezeichnet.

Komplexität

Boolesche Schaltkreise sind in der Komplexitätstheorie von Bedeutung, insbesondere im Teilgebiet der Schaltkreiskomplexität (englisch Circuit complexity).

Komplexitätsmaße für Schaltkreise

Es gibt unterschiedliche Maße für die Komplexität eines Schaltkreises:

Schaltkreisgröße (englisch circuit size): Die Anzahl der internen Knoten des Schaltkreises.
Schaltkreistiefe (englisch circuit depth): Die maximale Länge eines Pfades von einem Eingabegatter zu einem Ausgangsgatter.
Anzahl der Alternierungen von AND und OR Gattern (englisch number of alternations).
Ingrad / Ausgrad des Schaltkreises: Die maximale Anzahl an eingehenden / ausgehenden Kanten eines Knotens des Schaltkreises. Der Ingrad wird durch die Basis $\Upsilon$ beschränkt.

Komplexitätsklassen

Einige bedeutende Komplexitätsklassen können mit Hilfe boolescher Schaltkreise definiert werden.

Die Klasse NC und die dazugehörige Hierarchie ${\mbox{NC}}^{i}$
Die Klasse AC und die dazugehörige Hierarchie ${\mbox{AC}}^{i}$

Schaltkreis-Auswertungsproblem

Beim Auswerten eines booleschen Schaltkreises (englisch Circuit Value Problem) berechnet man für einen gegebenen Input-String, der allen Input-Gattern einen Wahrheitswert zuordnet, die Werte der Output-Gatter. Das Entscheidungsproblem, ob ein Output-Gatter eines Schaltkreises für eine gegebene Eingabe wahr ist, ist P-vollständig.

Erfüllbarkeitsproblem für Schaltkreise

Das Erfüllbarkeitsproblem für Schaltkreise (englisch circuit satisfiability problem) betrachtet einen booleschen Schaltkreis $C$ mit Basis $\Upsilon =\{\wedge ,\vee ,\neg \}$ und einem einzigen Output-Gatter und fragt, ob es eine Eingabe gibt, die dieses Gatter auf 1 setzt, d. h., ob es ein $X$ gibt, so dass $f_{C}(X)=1$ . Das Erfüllbarkeitsproblem für Schaltkreise ist NP-vollständig.

Literatur

K. Rüdiger Reischuk: Einführung in die Komplexitätstheorie: Band 1: Grundlagen Maschinenmodelle, Zeit- und Platzkomplexität, Nichtdeterminismus. Teubner Verlag, 1999, ISBN 978-3-519-12275-3, 2.2 Schaltkreis-Familien.
Christos H.Papadimitriou: Computational Complexity. Addison-Wesley, Reading/Mass, 1995, ISBN 978-0-201-53082-7, 4.3 Boolean functions and circuits & 8 Reductions and completeness (englisch).