À quoi servent les circuits à largeur d'arbre borné?

On peut parler de la largeur d' arbre d'un circuit booléen, la définissant comme la largeur d'arbre du graphe "moralisé" sur les fils (sommets) obtenu comme suit: connectez les fils $a$ et $b$ chaque fois que $b$ est la sortie d'une porte ayant $a$ entrée (ou vice versa); connectez les fils $a$ et $b$ chaque fois qu'ils sont utilisés comme entrées sur la même porte. Edit: on peut définir de manière équivalente la largeur d'arbre du circuit comme celle du graphe le représentant; si nous utilisons l'associativité pour réorganiser toutes les portes ET et OU pour avoir un fan-in au plus deux, la largeur d'arbre selon l'une ou l'autre définition est la même jusqu'à un facteur $3$ .

Il existe au moins un problème connu pour être insoluble en général mais traitable sur les circuits booléens de largeur d'arbre bornée: étant donné une probabilité pour que chacun des fils d'entrée soit défini sur 0 ou 1 (indépendamment des autres), calculez la probabilité que une certaine porte de sortie est 0 ou 1. Ceci est généralement # P-difficile par une réduction par exemple de # 2SAT, mais il peut être résolu dans PTIME sur des circuits dont la largeur d'arbre est supposée être inférieure à une constante, en utilisant l' algorithme d'arbre de jonction .

Ma question est de savoir s'il y a d' autres problèmes, au-delà du calcul probabiliste, qui sont connus pour être insolubles en général mais traitables pour les circuits de largeur d'arbre borné, ou dont la complexité peut être décrite en fonction de la taille du circuit et aussi de sa largeur d'arbre. Ma question n'est pas spécifique au cas booléen; Je m'intéresse également aux circuits arithmétiques sur d'autres semirings. Voyez-vous de tels problèmes?

Nous comprenons maintenant que pour toute borne fixe $k \in \mathbb{N}$ sur la largeur d'arbre, nous pouvons convertir tout circuit booléen de largeur d'arbre inférieur à $k$ en un circuit dit d-SDNNF , en temps linéaire et avec la dépendance de $k$ étant exponentielle seule.

Les soi-disant d-SDNNF sont des circuits satisfaisant aux conditions d'utilisation de la négation (uniquement aux feuilles), du déterminisme (les entrées des portes OU s'excluent mutuellement), de la décomposabilité (les entrées des portes ET dépendent des ensembles disjoints de variables ) et la structure (les portes ET divisent les variables de manière fixe tout au long du circuit, comme décrit par un arbre en V). Cette classe a été étudiée dans la compilation des connaissances et est connue pour apprécier le SAT tractable et le comptage de modèle tractable (recapture de l'évaluation et du comptage probabilistes), mais d'autres problèmes ont été étudiés pour cette classe tels que l' énumération , la quantification , etc.

Ainsi, une façon d'utiliser des limites sur la largeur d'arbre d'un circuit est de le convertir en cette classe d-SDNNF qui a des propriétés plus explicites en termes de sémantique du circuit et pour lesquelles il existe plusieurs résultats connus sur la tractabilité de diverses tâches.