Heuristiken zur Abschätzung der Effizienz von reduzierten geordneten binären Entscheidungsdiagrammen?

8

Reduziertes bestellt Binary Decision Diagrams (ROBDD) ist eine effiziente Datenstruktur für die Darstellung von Booleschen Funktionen mehreren Variablen . Ich möchte eine Vorstellung davon bekommen, wie effizient sie sind.f(x1,x2,...,xn)

Zum Beispiel wissen wir für die Datenkomprimierung, dass Daten mit niedriger Entropie (einige Symbole erscheinen häufiger als andere, viele Wiederholungen) sehr gut komprimiert werden können, während vollständig zufällige Daten nicht komprimiert werden können.

Gibt es eine analoge Intuition, um abzuschätzen, wie effizient ROBDDs eine bestimmte Boolesche Formel darstellen können?

Ich habe zum Beispiel gehört, dass die Multiplikation von Bit-Zahlen nicht effizient dargestellt werden kann, die minimale ROBDD-Größe ist in n exponentiell . Kennen Sie ein intuitives Argument, das erklärt, warum dies der Fall ist?nn

Verwandte Frage: Intuition über die Effizienz von BDDs, die Zahlen berechnen (BDDs mit mehreren Terminals usw.)

Heinrich Apfelmus
quelle

Antworten:

7

Es gibt eine Beziehung zwischen der Breite eines OBDD für eine Funktion und der Kommunikationskomplexität eines Einweg-Kommunikationsprotokolls für die Best-Case-Partition von Variablen für f (siehe E. Kushilevitz und N. Nisan. Kommunikationskomplexität. Universität Cambridge Press, 1997 ).ff

Dies ist ein leistungsstarkes Werkzeug zum Nachweis von OBDDs mit exponentieller Größe für verschiedene Funktionen (zusammen mit Mitautoren haben wir diese Methode verwendet, um zu beweisen, dass Bipartiteness für OBDDs schwierig ist, siehe hier ). Wenn im Grunde eine OBDD mit einer Breite von höchstens w existiert , die f löst , dann ist κ b e s t ( f ) log w . Ich denke, dies ist intuitiver in Bezug auf die Kommunikationskomplexität zu denken als in Bezug auf OBDD.ϵwfκbest(f)logw

Sylvain Peyronnet
quelle
3
Ah, also teilen Sie die Eingaben von in zwei Teile f ( x 1 , , x k , y 1 , , y l ) . Dann folgt Alice einfach den Zweigen des BDD auf ihrer Eingabe x und teilt Bob ihren letzten Knoten mit, der die Berechnung mit y abschließt . Da die Breite w ist , braucht sie höchstens log wff(x1,,xk,y1,,yl)xywlogwBits, um ihren Knoten zu kommunizieren. Nett! Dies hängt etwas mit der "Blockdiagramm" -Antwort von Radu zusammen, da das Vorhandensein eines solchen Blockdiagramms sicherlich eine geringe Kommunikationskomplexität impliziert. (Die Umkehrung "kleine Kommunikationskomplexität => kleine Breite" gilt jedoch nicht unbedingt, oder?)
Heinrich Apfelmus
Kleinere Anfrage: Kennen Sie eine Version Ihres verlinkten Papiers , die frei verfügbar ist, dh nicht hinter einer Paywall?
Heinrich Apfelmus
Klar, hier ist ein Link: sylvain.berbiqui.org/llmpr-full.pdf
Sylvain Peyronnet
"(Die Umkehrung" kleine Kommunikationskomplexität => kleine Breite "gilt jedoch nicht unbedingt, oder?)" In der Tat gilt sie nicht unbedingt.
Sylvain Peyronnet
6

f(x1,,xn)b1,,bnbkxkbk1bk+1bnffbkbk1

x1,,xk1knk

nf(x1,,xn)xkk1,2,,k1k1kk1kkk+11n

fgfmgnO(mn)O(m+n)

Radu GRIGore
quelle
fbi
2

Zur Berechnung von Zahlen sollten Sie sich MTBDDs (Multi Terminal BDDs) ansehen, eine Datenstruktur, die für die (probabilistische) Modellprüfung verwendet wird. Siehe zum Beispiel Darstellungen diskreter Funktionen, Sasao, Tsutomu; Fujita, Masahira (Hrsg.), Springer, 1996 , Kapitel 4, von Clarke et al. handelt von MTBDDs und Hybrid Decision Diagram.

Sylvain Peyronnet
quelle
2

In TAoCP 4 Faszikel 1 erwähnt Knuth dies ebenfalls

  • f(x1,x2,,xn)nO(n2)fn+1x1+x2++xn{0,1,2,n}2n
  • g(x1,x2):=f(x1,x2,x2)

f(x1,x2,x3):=(2x1+5x2+3x37)f(x1+x2++x107)

Heinrich Apfelmus
quelle
Es gibt auch einen Teil über "böse" Funktionen.
Radu GRIGore