Binäres Entscheidungsdiagramm

Einfache Sprache

Def. Binäres Entscheidungsdiagramm

Ein Binäres Entscheidungsdiagramm oder auch branching program ist ein gerichteter azyklischer Graph. Die Knoten sind sind entweder mit Variablennamen beschriftet, so genannte Abfrageknoten oder sie sind so genannte Ausgabeknoten beschriftet mit $1$ und $0$, so genannte $1$-Kante bzw. $0$-Kante. Jeder Abfrageknoten hat zwei ausgehende Kanten, beschriftet mit $1$ und $0$. Die Ausgabeknoten haben keine ausgehenden Kanten. Die Wurzel ist der so genannte Startknoten.

Gegeben ein branching program und eine Variablenbelegung, kann man der Wert der Boolesche Funktion, die das branching program räpresentiert, herausfinden, indem ausgehen von dem Startknoten abhängig von der konkreten Belegung der Variable der Abfrageknoten ein Weg bis zu einem Ausgabeknoten gegangen wird.

Bekannte Probleme

Die Ausgabe für eine branching program zu berechnen liegt in LSPACE wie der Satz BRANCHING-PROG in L besagt.