If BoolVariable is true, "jump" to Then-Address. If BoolVariable is false, jump to Else-Address.
Programs start on address 2. Address0 represents false, Address1 represents true.
Lets start with the easiest:
0: false
1: true
2: ITE(0, 0, 1)
0: false
1: true
2: ITE(0, 3, 4)
3: ITE(1, 1, 0)
4: ITE(1, 0, 1)
At these small sizes, it doesn't seem like branching programs / 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 "addition" or "multiplication") are in fact correct.
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.
----------
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 "variable 0" first, then "variable 1", then "variable 2"). If you satisfy these properties, then you can "solve" the 3SAT / Satisfiability problem with the simple logic:
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.
This is because under an ORBDD, if the BDD is unsatisfiable, it'd be represented as:
0: false
1: true
2: ITE(0, 0, 0)
--------
It turns out that the #P-complete "counting solutions" is solvable in O(n) time and O(n) space in BDDs (!!!). I can step you through the XOR program for instance. I'll "reorder" the program so that we can just count solutions from top-to-bottom (0, 1, 4, 3, 2).
0: false <-- 0 solutions
1: true <-- 1 solution
4: ITE(1, 0, 1) <--- Then-branch has 0 solutions, but Else-branch has 1 solution. 0 + 1 == 1 solution
3: ITE(1, 1, 0) <--- Then-branch has 0 solutions, but Else-branch has 1 solution. 0 + 1 == 1 solution
2: ITE(0, 3, 4) <--- Then-branch has 1 solution + else-branch has 1 solution == 2 total solutions
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).
----------
If you "skip" a variable, there's a multiplier of 2^(number of skipped variables). For example, lets say we have "Var0 XOR Var4", (5 total variables, but Var1/Var2/Var3 are ignored).
0: false <-- 0 solutions
1: true <-- 1 solution
4: ITE(4, 0, 1) <-- 1 solution
3: ITE(4, 1, 0) <-- 1 solution
2: ITE(0, 3, 4) <-- 2^(#Skipped Variables) * (1+1) solutions == 2^3 * 2 == 16 solutions total
I'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'd much rather use BDDs for this problem rather than the truth table.
------
Alas: we don't get "something for noting". 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 "variable 0" ??) is itself an NP-complete problem.
So no shortcuts to solving NP-complete stuff at all. Nonetheless, if someone needs to "easily" solve the #P-class of problems (ie: counting-NP completeness). That is: "find the total number of solutions to the 3SAT problem", or "Find the best solution to the 3SAT problem", for optimizing problems and/or counting problems... BDDs are a very good data-structure for that.
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)
In practice: you start with simple ORBDDs (such as AND, OR, XOR, SUM, MULTIPLY), you combine ORBDDs with the "synthesis" algorithm... which creates new ORBDDs that combines the previous ones. The output is provably ordered-and-reduced still.
That is to say: you can "maintain" ORBDDs rather easily in practice. In theory, each synthesis step could blow up the BDD exponentially... but in practice, there are many circuits / algorithms where the ORBDD remains small and usable.