Heurísticas para estimar a eficiência de diagramas de decisão binária com ordem reduzida?

Os diagramas de decisão binária ordenada reduzida (ROBDD) são uma estrutura de dados eficiente para representar funções booleanas de várias variáveis . Eu gostaria de ter uma intuição de quão eficientes eles são.$f(x_1,x_2,...,x_n)$

Por exemplo, para compactação de dados, sabemos que dados com baixa entropia (alguns símbolos aparecem com mais frequência que outras, muitas repetições) podem ser compactados muito bem, enquanto dados completamente aleatórios não podem ser compactados.

Existe uma intuição análoga para estimar com que eficiência os ROBDDs podem representar uma dada fórmula booleana?

Por exemplo, ouvi dizer que a multiplicação de números de bits não pode ser representada com eficiência, o tamanho mínimo do ROBDD é exponencial em . Você conhece um argumento intuitivo que explica por que esse é o caso?$n$$n$

Pergunta relacionada: intuição sobre a eficiência de BDDs que calculam números (múltiplos BDDs terminais, etc.)

Há uma relação entre a largura de um OBDD para uma função e a complexidade da comunicação de um protocolo de comunicação unidirecional para a melhor partição de variáveis ​​para (consulte E. Kushilevitz e N. Nisan. Complexidade da comunicação. Universidade de Cambridge Press, 1997 ).$f$$f$

Esta é uma ferramenta poderosa para provar OBDDs de tamanho exponencial para várias funções (juntamente com os co-autores, usamos este método para provar que -bipartiteness é difícil para OBDDs, veja aqui ). Basicamente, se existe um OBDD de largura no máximo que resolve , então . Eu acho que isso é mais intuitivo em termos de complexidade da comunicação do que em OBDD.w f κ b e s t ( f ) ≤ log $\epsilon$$w$$f$$\kappa_{best}(f) \leq \log w$

Uma maneira de calcular uma função booleana é ter uma cadeia de blocos de circuitos booleanos modo que leia apenas (das entradas) e esteja conectado apenas a e . Uma das saídas do último bloco é o valor de . O teorema M no fascículo 1 do TAoCP 4 diz que o BDD de deve ser grande se, para todos esses circuitos, você precisar de muitos links para trás (de a ).b 1 , … , b n b k x k b k - 1 b k + 1 b n f f b k b k - $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}$

Em outras palavras, para que o BDD seja pequeno, deve haver uma maneira de resumir as informações em para . A largura do BDD corresponde ao mais difícil de compactar, intuitivamente. 1 ≤ k ≤ n $x_1,\ldots,x_k$$1\le k\le n$$k$

(Um exemplo dado no TAoCP é o seguinte: imagine um ciclo de comprimento e uma função booleana que diz "não há nó que tenha a mesma cor dos dois vizinhos", onde diz se o nó é preto ou branco. Em seguida, o 'resumo' depois de examinar os nós deve armazenar a cor , , e se você já notou uma violação. e de modo que você pode verificar se a propriedade é violada em uma vez que você também ver . você precisa def ( x 1 , … , x n ) x k k 1 , 2 , … , k 1 k - 1 k k - 1 k k k + 1 1 $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$para que você possa verificar se a propriedade foi violada em , quando chegar ao final.)$n$

Além disso, se você se preocupa com operações entre BDDs, em seguida, fazer uma operação binária entre e , onde é representado por um BDD que tem nós e é representado por um BDD que tem nós leva tempo, mas tende levar apenas tempo para funções que você encontra na prática. Não estou ciente de uma versão precisa do que acabei de dizer, mas estaria interessado se houver.g f m g n O ( m n ) O ( m + n $f$$g$$f$$m$$g$$n$$O(mn)$$O(m+n)$

Para calcular números, você deve considerar os MTBDDs (Multi Terminal BDDs), uma estrutura de dados usada para verificação de modelo (probabilístico). Veja, por exemplo, Representações de Funções Discretas, Sasao, Tsutomu; Fujita, Masahira (Eds.), Springer, 1996 , capítulo 4, de Clarke et al. é sobre MTBDDs e diagrama de decisão híbrido.

No TAoCP 4 fascículo 1 , Knuth também 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)$

Isso mostra que funções como possuem BDDs eficientes, pois é uma especialização da função simétrica .f ( x 1 + x 2 + ⋯ + x 10 ≥ 7 $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)$