¿Heurística para estimar la eficiencia de los diagramas de decisión binarios ordenados reducidos?

Diagramas reducido Ordenadas decisión binaria (ROBDD) son una estructura de datos eficiente para la representación de funciones booleanas de múltiples variables . Me gustaría tener una intuición de cuán eficientes son.$f(x_1,x_2,...,x_n)$

Por ejemplo, para la compresión de datos, sabemos que los datos con baja entropía (algunos símbolos aparecen con más frecuencia que otros, muchas repeticiones) se pueden comprimir muy bien, mientras que los datos completamente aleatorios no se pueden comprimir.

¿Existe una intuición análoga para estimar cuán eficientemente los ROBDD pueden representar una fórmula booleana dada?

Por ejemplo, he escuchado que la multiplicación de números de bits no se puede representar de manera eficiente, el tamaño mínimo de ROBDD es exponencial en n . ¿Conoces un argumento intuitivo que explique por qué este es el caso?$n$$n$

Pregunta relacionada: intuición sobre la eficiencia de los BDD que calculan números (múltiples BDD terminales, etc.)

Existe una relación entre el ancho de un OBDD para una función y la complejidad de comunicación de un protocolo de comunicación unidireccional para la mejor partición de variables para f (ver E. Kushilevitz y N. Nisan. Complejidad de comunicación. Universidad de Cambridge Prensa, 1997 ).$f$$f$

Esta es una herramienta poderosa para probar OBDD de tamaño exponencial para diversas funciones (junto con los coautores, utilizamos este método para demostrar que -bipartiteness es difícil para los OBDD, ver aquí ). Básicamente, si existe un OBDD de ancho como máximo w que resuelve f , entonces κ b e s t ( f ) ≤ log w . Creo que es más intuitivo pensar en términos de complejidad de comunicación en lugar de OBDD.$\epsilon$$w$$f$$\kappa_{best}(f) \leq \log w$

$f(x_1,\ldots,x_n)$$b_1,\ldots,b_n$$b_k$$x_k$$b_{k-1}$$b_{k+1}$$b_n$$f$$f$$b_k$$b_{k-1}$

$x_1,\ldots,x_k$$1\le k\le n$$k$

$n$$f(x_1,\ldots,x_n)$$x_k$$k$$1,2,\ldots,k$$1$$k-1$$k$$k-1$$k$$k$$k+1$$1$$n$

$f$$g$$f$$m$$g$$n$$O(mn)$$O(m+n)$

Para calcular los números, debe observar los MTBDD (Multi Terminal BDD), una estructura de datos utilizada para la verificación del modelo (probabilístico). Véanse, por ejemplo, Representaciones de funciones discretas, Sasao, Tsutomu; Fujita, Masahira (Eds.), Springer, 1996 , el capítulo 4, por Clarke et al. trata sobre MTBDD y Diagrama de decisión híbrido.

En TAoCP 4 fascículo 1 , Knuth también menciona que

• $f(x_1,x_2,\dots,x_n)$$n$$\mathcal O(n^2)$$f$$n+1$$x_1+x_2+\dots+x_n \in \lbrace 0,1,2,\dots n\rbrace$$2^n$
• $g(x_1,x_2) := f(x_1,x_2,x_2)$

$f(x_1,x_2,x_3) := (2x_1 + 5x_2 + 3x_3 \ge 7)$$f$$(x_1 + x_2 + \dots + x_{10} \ge 7)$