# What are bounded-treewidth circuits good for?

One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $$a$$ and $$b$$ whenever $$b$$ is the output of a gate having $$a$$ as input (or vice-versa); connect wires $$a$$ and $$b$$ whenever they are used as inputs to the same gate. Edit: one can equivalently define the treewidth of the circuit as that of the graph representing it; if we use associativity to rewite all AND and OR gates to have fan-in at most two, the treewidth according to either definition is the same up to a factor $$3$$.

There is at least one problem that is known to be untractable in general but tractable on Boolean circuits of bounded treewidth: given a probability for each of the input wires to be set to 0 or 1 (independently from the others), compute the probability that a certain output gate is 0 or 1. This is generally #P-hard by a reduction from e.g. #2SAT, but it can be solved in PTIME on circuits whose treewidth is assumed to be less than a constant, using the junction tree algorithm.

My question is to know whether there are other problems, beyond probabilistic computation, that are known to be intractable in general but tractable for bounded-treewidth circuts, or whose complexity can be described as a function of the circuit size and also of its treewidth. My question is not specific to the Boolean case; I am also interested in arithmetic circuits over other semirings. Do you see any such problems?

• For the case of Boolean circuits with negation (so it doesn't generalize to arithmetic circuits), I now realize that testing satisfiability or universality is in PTIME. Without negation this is always the case, but with negation this is generally NP-hard (trivially by reduction from SAT) but it is in PTIME (as a special case of probabilistic inference) for the case of bounded-treewidth circuits. But still, this doesn't satisfy me a lot as it is essentially the same problem... – a3nm Sep 3 '14 at 8:26

We now understand that for any fixed bound $$k \in \mathbb{N}$$ on the treewidth, we can convert any Boolean circuit of treewidth less than $$k$$ to a so-called d-SDNNF circuit, in linear time and with the dependency on $$k$$ being singly exponential.