Computation graphs and graph computation (2020)
Missing my favorite graphs: the binary decision diagram &#x2F; Branching program. BDDs &#x2F; Branching programs consist of nodes called &quot;ITE Nodes&quot;, meaning &quot;If &#x2F; Then &#x2F; Else&quot;. Roughly ITE(BoolVariable, Then-Address, Else-Address).<p>If BoolVariable is true, &quot;jump&quot; to Then-Address. If BoolVariable is false, jump to Else-Address.<p>Programs start on address 2. Address0 represents false, Address1 represents true.<p>Lets start with the easiest:<p><pre><code>    0: false
    1: true
    2: ITE(0, 0, 1) 
</code></pre>
This program above represents &quot;if(Variable[0]){ return false; } else { return true}&quot;. Can&#x27;t get any easier than this!! Okay, lets make things a wee bit harder.<p><pre><code>    0: false
    1: true
    2: ITE(0, 3, 4)
    3: ITE(1, 1, 0)
    4: ITE(1, 0, 1)
</code></pre>
This program represents Var0 XOR Var1.<p>At these small sizes, it doesn&#x27;t seem like branching programs &#x2F; BDDs are very useful. However, it turns out that BDDs can in practice, represent 100+ variable graphs efficiently (!!!). As such, your CAD tools use BDDs in practice to prove whether or not boolean functions (such as &quot;addition&quot; or &quot;multiplication&quot;) are in fact correct.<p>IMO, Binary Decision Diagrams sit at the edge of NP-completeness vs Efficiency. Clearly, BDDs represent the 3-SAT problem. But in practice, most algorithms (finding a solution for example) can take place very efficiently.<p>----------<p>For example: the ORBDD (Ordered, Reduced, BDD) has a property such that no node is redundant, and all variables are ordered. (That is, you visit &quot;variable 0&quot; first, then &quot;variable 1&quot;, then &quot;variable 2&quot;). If you satisfy these properties, then you can &quot;solve&quot; the 3SAT &#x2F; Satisfiability problem with the simple logic:<p>1. Start at the start of the program (aka: line 2).
2. Does the ITE() branch to non-zero (aka: non-false value) ?? Then your BDD is satisfiable. Period.<p>This is because under an ORBDD, if the BDD is unsatisfiable, it&#x27;d be represented as:<p><pre><code>    0: false
    1: true
    2: ITE(0, 0, 0)
</code></pre>
Because ORBDDs are &quot;reduced&quot; (ie: no redundant nodes). As such, solving 3SAT with ORBDDs is in fact, a O(1) operation.<p>--------<p>It turns out that the #P-complete &quot;counting solutions&quot; is solvable in O(n) time and O(n) space in BDDs (!!!). I can step you through the XOR program for instance. I&#x27;ll &quot;reorder&quot; the program so that we can just count solutions from top-to-bottom (0, 1, 4, 3, 2).<p><pre><code>    0: false &lt;-- 0 solutions
    1: true &lt;-- 1 solution
    4: ITE(1, 0, 1) &lt;--- Then-branch has 0 solutions, but Else-branch has 1 solution. 0 + 1 == 1 solution
    3: ITE(1, 1, 0) &lt;--- Then-branch has 0 solutions, but Else-branch has 1 solution. 0 + 1 == 1 solution
    2: ITE(0, 3, 4) &lt;--- Then-branch has 1 solution + else-branch has 1 solution == 2 total solutions
</code></pre>
You&#x27;ll need a topological bucket &#x2F; radix sort (O(n) sorting algorithm) to &quot;visit&quot; the ITE-statements in the correct order. But if done so, you can &quot;obviously&quot; count the solutions in just O(n) time!!<p>Because all ITE statements have their variable number associated with them in the 1st position (ITE(5, X, Y) should be visited before ITE(2, X, Y)), its a simple matter of O(n) bucket or radix sort on the variable number. (No need for a graph-based topological sort).<p>----------<p>If you &quot;skip&quot; a variable, there&#x27;s a multiplier of 2^(number of skipped variables). For example, lets say we have &quot;Var0 XOR Var4&quot;, (5 total variables, but Var1&#x2F;Var2&#x2F;Var3 are ignored).<p><pre><code>    0: false &lt;-- 0 solutions
    1: true &lt;-- 1 solution
    4: ITE(4, 0, 1) &lt;-- 1 solution
    3: ITE(4, 1, 0) &lt;-- 1 solution
    2: ITE(0, 3, 4) &lt;-- 2^(#Skipped Variables) * (1+1) solutions == 2^3 * 2 == 16 solutions total
</code></pre>
We get 16 total solutions. (ex: 0_000_1, 0_001_1, ... 0_111_1, then 1_000_0, 1_001_0, ... 1_111_0).<p>I&#x27;m still using functions that are easily verifiable by hand. But you can imagine that when these BDDs get into Megabytes or Gigabytes territory, you&#x27;d much rather use BDDs for this problem rather than the truth table.<p>------<p>Alas: we don&#x27;t get &quot;something for noting&quot;. It turns out that _making an ORBDD in the first place_ is an NP-complete problem in of itself (!!!). In fact, even finding a good ordering (which variable should be &quot;variable 0&quot; ??) is itself an NP-complete problem.<p>So no shortcuts to solving NP-complete stuff at all. Nonetheless, if someone needs to &quot;easily&quot; solve the #P-class of problems (ie: counting-NP completeness). That is: &quot;find the total number of solutions to the 3SAT problem&quot;, or &quot;Find the best solution to the 3SAT problem&quot;, for optimizing problems and&#x2F;or counting problems... BDDs are a very good data-structure for that.<p>Traditionally, ORBDDs are used for proving that two truth tables are identical, without storing the 2^128 solutions needed per bit of a 64-bit + 64-bit boolean function. The BDD is often several orders of magnitude smaller than the truth table (not in all cases. Just in most cases we come across in making chips)<p>In practice: you start with simple ORBDDs (such as AND, OR, XOR, SUM, MULTIPLY), you combine ORBDDs with the &quot;synthesis&quot; algorithm... which creates new ORBDDs that combines the previous ones. The output is provably ordered-and-reduced still.<p>That is to say: you can &quot;maintain&quot; ORBDDs rather easily in practice. In theory, each synthesis step could blow up the BDD exponentially... but in practice, there are many circuits &#x2F; algorithms where the ORBDD remains small and usable.