Direkt zum Inhalt

Lexikon der Mathematik: Branchingprogramm

auch Verzweigungsprogramm, eine Darstellungsform für Boolesche Funktionen.

Ein Branchingprogramm auf der Variablenmenge Xn = {x1, …, xn} besteht aus einem gerichteten azyklischen Graphen G = (V, E), dessen Knoten zwei (innere Knoten) oder keine (Senken) ausgehende Kanten haben, und einer Markierung der Knoten und Kanten. Jeder innere Knoten ist mit einer Variablen aus Xn markiert, jede Senke mit einer Konstanten aus {0, 1}. Für jeden inneren Knoten erhält eine ausgehende Kante die Markierung 0 und die andere die Markierung 1.

Jeder Knoten v stellt eine Boolesche Funktion fv auf Xn dar. Zur Auswertung (Auswertungsproblem) von fv auf a ∈ {0, 1}n wird an v gestartet und an xi-Knoten die mit ai markierte Kante gewählt.

Dann ist fv(a) gleich der Marke der schließlich erreichten Senke. Die Klasse der mit polynomiell großen Branchingprogrammen darstellbaren Sprachen ist die nichtuniforme Variante der Klasse der mit logarithmischer Raumkomplexität berechenbaren Sprachen. Branchingprogramme mit bestimmten Restriktionen dienen als Datenstruktur für Boolesche Funktionen, die viele Anwendungen, insbesondere bei der Verifikation, finden.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos