auch Verzweigungsprogramm, eine Darstellungsform für Boolesche Funktionen.

Ein Branchingprogramm auf der Variablenmenge X_n = {x₁, …, x_n} 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 X_n 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 f_v auf X_n dar. Zur Auswertung (Auswertungsproblem) von f_v auf a ∈ {0, 1}ⁿ wird an v gestartet und an x_i-Knoten die mit a_i markierte Kante gewählt.

Dann ist f_v(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.