Heuristiken zum Schätzen der Effizienz von binären Entscheidungsdiagrammen mit reduzierten Ordnungen?

Question

Reduced Ordered Binary Decision Diagrams (ROBDD) sind eine effiziente Datenstruktur für boolesche Funktionen mehrerer Variablen f(x1,x2,...,xn). Ich würde gerne eine Intuition für wie effizient sie sind. Für die Datenkompression wissen wir beispielsweise, dass Daten mit niedriger Entropie (einige Symbole, die öfter vorkommen als andere, viele Wiederholungen) sehr gut komprimiert werden können, während völlig zufällige Daten nicht komprimiert werden können.

Gibt es eine analoge Intuition für die Schätzung, wie effizient ROBDDs eine gegebene boolesche Formel darstellen können? Literatur zu diesem Thema (vorzugsweise online)?

Answer 1

Es gibt Artikel im Wikipedia-Artikel Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams, die Ober- und Untergrenzen für bestimmte Funktionsklassen (symmetrisch, binäre Arithmetik) angeben. Ich denke, dass im durchschnittlichen Fall 2n*log n >= 2^k gilt, wobei n die Anzahl der Knoten im Diagramm und k die Anzahl der Variablen der Funktion ist. Die obere Grenze ist n <= 2^(k+1) - 1 erreicht mit dem vollständigen Binärbaum.