Para que servem os circuitos de largura de árvore limitada?

Pode-se falar da treewidth de um circuito booleano, definindo-o como o treewidth do gráfico "moralizada" em fios (vértices) obtida da seguinte forma: os fios de conexão $a$ e $b$ quando $b$ é a saída de uma porta tendo $a$ como entrada (ou vice-versa); fios de conexão $a$ e $b$ quando eles são utilizados como entradas para a mesma porta. Editar: pode-se definir equivalentemente a largura da árvore do circuito como a do gráfico que o representa; se usarmos a associatividade para recriar todos os portões AND e OR para ter fan-in no máximo dois, a largura da árvore de acordo com qualquer definição é a mesma até um fator $3$ .

Há pelo menos um problema que se sabe não ser tratável em geral, mas tratável em circuitos booleanos de largura de árvore limitada: dada a probabilidade de cada um dos fios de entrada ser definido como 0 ou 1 (independentemente dos outros), calcule a probabilidade de que uma determinada porta de saída é 0 ou 1. Isso geralmente é # P-rígido por uma redução de, por exemplo, # 2SAT, mas pode ser resolvido em PTIME em circuitos cuja largura de árvore é assumida como menor que uma constante, usando o algoritmo da árvore de junção .

Minha pergunta é saber se existem outros problemas, além da computação probabilística, que são conhecidos por serem intratáveis ​​em geral, mas tratáveis ​​por circuitos com largura de árvore limitada ou cuja complexidade pode ser descrita como uma função do tamanho do circuito e também de sua largura de árvore. Minha pergunta não é específica para o caso booleano; Também estou interessado em circuitos aritméticos em relação a outros semirriscos. Você vê algum desses problemas?

$k \in \mathbb{N}$$k$$k$

Os chamados d-SDNNFs são circuitos que satisfazem as condições de uso de negação (apenas nas folhas), determinismo (as entradas para os portões OR são mutuamente exclusivas), decomposição (as entradas para os portões AND dependem de conjuntos disjuntos de variáveis ) e estrutura (os portões AND dividem as variáveis ​​de maneira fixa em todo o circuito, conforme descrito por uma árvore em V). Essa classe foi estudada em compilação de conhecimento e é conhecida por contar com SAT tratável e contagem de modelo tratável (recapturando avaliação e contagem probabilística), mas outros problemas foram estudados para essa classe, como enumeração , quantificação etc.

Portanto, uma maneira de usar limites na largura de árvore de um circuito é convertê-lo nessa classe d-SDNNF que possui propriedades mais explícitas em termos de semântica do circuito e para as quais existem vários resultados conhecidos sobre a rastreabilidade de várias tarefas.