¿Para qué sirven los circuitos de ancho de árbol acotado?

Se puede hablar de la treewidth de un circuito booleano, definiéndola como la treewidth del gráfico "moralizado" en los alambres (vértices) obtenido como sigue: los cables de conexión $a$ y $b$ cuando $b$ es la salida de una puerta que tiene $a$ como entrada (o viceversa); cables de conexión $a$ y $b$ cada vez que se utilizan como entradas a la misma puerta. Editar: se puede definir de manera equivalente el ancho de árbol del circuito como el del gráfico que lo representa; Si usamos asociatividad para reescribir todas las compuertas AND y OR para tener un fan-in como máximo dos, el ancho del árbol según cualquiera de las definiciones es el mismo hasta un factor $3$ .

Hay al menos un problema que se sabe que no se puede tratar en general, pero que se puede tratar en los circuitos booleanos de ancho de árbol acotado: dada la probabilidad de que cada uno de los cables de entrada se establezca en 0 o 1 (independientemente de los demás), calcule la probabilidad de que cierta puerta de salida es 0 o 1. Esto generalmente es # P-duro por una reducción de, por ejemplo, # 2SAT, pero se puede resolver en PTIME en circuitos cuyo ancho de árbol se supone menor que una constante, utilizando el algoritmo de árbol de unión .

Mi pregunta es saber si hay otros problemas, más allá del cálculo probabilístico, que se sabe que son intratables en general pero manejables para los cortes de ancho de árbol limitado, o cuya complejidad puede describirse como una función del tamaño del circuito y también de su ancho de árbol. Mi pregunta no es específica del caso booleano; También estoy interesado en circuitos aritméticos sobre otros semirremolques. ¿Ves alguno de estos problemas?

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

Los llamados d-SDNNF son circuitos que satisfacen condiciones sobre el uso de la negación (solo en las hojas), determinismo (las entradas a las compuertas OR son mutuamente excluyentes), descomponibilidad (las entradas a las compuertas AND dependen de conjuntos de variables disjuntos ) y estructura (las compuertas AND dividen las variables de alguna manera fija en todo el circuito, como se describe en un árbol v). Esta clase se ha estudiado en la compilación de conocimientos y se sabe que disfruta del SAT manejable y el conteo de modelos manejables (recapturando la evaluación probabilística y el conteo), pero se han estudiado otros problemas para esta clase, como la enumeración , la cuantificación , etc.

Entonces, una forma de usar límites en el ancho de árbol de un circuito es convertirlo a esta clase d-SDNNF que tiene propiedades más explícitas en términos de la semántica del circuito, y para la cual hay varios resultados conocidos sobre la capacidad de seguimiento de varias tareas.