<p>We <a href="https://arxiv.org/abs/1709.06188" rel="noreferrer">now understand</a> that for any fixed bound <span class="math-container">$k \in \mathbb{N}$</span> on the treewidth, we can convert any Boolean circuit of treewidth less than <span class="math-container">$k$</span> to a so-called <em>d-SDNNF</em> circuit, in linear time and with the dependency on <span class="math-container">$k$</span> being singly exponential.</p>

<p>The so-called d-SDNNFs are circuits satisfying conditions on the use of negation (only at the leaves), determinism (the inputs to OR-gates are mutually exclusive), decomposability (the inputs to AND-gates depend on disjoint sets of variables), and stucturedness (the AND-gates split the variables in some fixed way throughout the circuit, as described by a v-tree). This class has been studied in <a href="https://en.wikipedia.org/wiki/Knowledge_compilation" rel="noreferrer">knowledge compilation</a> and is known to enjoy tractable SAT and tractable model counting (recapturing probabilistic evaluation and counting), but other problems have been studied for this class such as <a href="https://arxiv.org/abs/1702.05589" rel="noreferrer">enumeration</a>, <a href="https://arxiv.org/abs/1807.04263" rel="noreferrer">quantification</a>, etc.</p>

<p>So one way to use bounds on the treewidth of a circuit is to convert it to this d-SDNNF class which has more explicit properties in terms of the circuit semantics, and for which there are several known results on the tractability of various tasks.</p>

CC BY-SA 4.0
2018-10-29T16:40:04.243Z
2018-10-29T16:40:04.243Z
Antoine Amarilli 'a3nm'
<p>One can talk of the <a href="https://en.wikipedia.org/wiki/Treewidth" rel="noreferrer">treewidth</a> of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires <span class="math-container">$a$</span> and <span class="math-container">$b$</span> whenever <span class="math-container">$b$</span> is the output of a gate having <span class="math-container">$a$</span> as input (or vice-versa); connect wires <span class="math-container">$a$</span> and <span class="math-container">$b$</span> whenever they are used as inputs to the same gate. <strong>Edit:</strong> 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 <span class="math-container">$3$</span>.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Junction_tree_algorithm" rel="noreferrer">junction tree algorithm</a>.</p>

<p>My question is to know whether there are <em>other</em> 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 <a href="https://en.wikipedia.org/wiki/Arithmetic_circuit" rel="noreferrer">arithmetic circuits</a> over other semirings. Do you see any such problems?</p>

CC BY-SA 3.0
2014-09-03T08:26:09.710Z
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...
Antoine Amarilli 'a3nm'
<circuit-complexity><pr.probability><treewidth><arithmetic-circuits>
What are bounded-treewidth circuits good for?
Antoine Amarilli 'a3nm'
# What are bounded-treewidth circuits good for?

(Asked by: username_0 on 2014-08-28)

One can talk of the [treewidth](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Arithmetic_circuit) over other semirings. Do you see any such problems?

**Tags:** circuit-complexity, pr.probability, treewidth, arithmetic-circuits
> **Comments:**
> **username_0**: 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...  

---

## 1 answers

### Answer by username_0 on 2018-10-29. Score: 9 | Accepted answer

We [now understand](https://arxiv.org/abs/1709.06188) 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.

The so-called d-SDNNFs are circuits satisfying conditions on the use of negation (only at the leaves), determinism (the inputs to OR-gates are mutually exclusive), decomposability (the inputs to AND-gates depend on disjoint sets of variables), and stucturedness (the AND-gates split the variables in some fixed way throughout the circuit, as described by a v-tree). This class has been studied in [knowledge compilation](https://en.wikipedia.org/wiki/Knowledge_compilation) and is known to enjoy tractable SAT and tractable model counting (recapturing probabilistic evaluation and counting), but other problems have been studied for this class such as [enumeration](https://arxiv.org/abs/1702.05589), [quantification](https://arxiv.org/abs/1807.04263), etc.

So one way to use bounds on the treewidth of a circuit is to convert it to this d-SDNNF class which has more explicit properties in terms of the circuit semantics, and for which there are several known results on the tractability of various tasks.


---

