I wouldn't do it justice[1], it deserves a blog post or a book [2] but in general solving almost any boolean algebra problem, in hundreds, and hundreds of thousands variables, very efficiently and in very compact representation (via ordered sparse bit vectors[3]).
While with Karnaugh maps you can simplify a boolean function with a few variables, BDDs can solve for thousands, fast.
And no need to explain applications of high-dimensional boolean algebra on HN, with boolean algebra you can solve any logic problem expressed as boolean function, any combinatorial problem (except for those with nasty functions), classic graph theory problems.
Surprisingly it allows to solve optimization problems[4], like boolean programming, SAT solver, max independent set or max cut in graphs, very efficiently, it can be used in something like belief propagation or lattice induction for inference, but if that's not enough you can use it for random number generation, lossless compression, perfect hashing, etc, etc.
I haven't seen such a versatile data structure elsewhere, most of the other things developed in the last 35 years, like the ones in the comment below are solving special cases, BDD is truly one of the most fundamental and severely underrated "swiss army knives" (that is in CS, EE people know it very well in logic synthesis and verification, BDD's first "killer app").
It's probably easier to list what you can't do with BDD, kind of like what you can't do with (high-dimensional) boolean logic.
I think it skipped the radar of CompSci community at large because it was too quickly siloed into "that circuit analysis/verification tool used by electrical engineers".
Yes, it's "just" a DAG but with very particular (and very simple) constraints which allow it to solve infinite variety of problems in a very elegant and surprising way [5].
[1] it's really worth watching the lecture on BDDs by Don Knuth , starting around 13:32, his enthusiasm is contagious: https://www.amazon.com/Art-Computer-Programming-Combinatoria...
There is a free preprint here https://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz
While with Karnaugh maps you can simplify a boolean function with a few variables, BDDs can solve for thousands, fast.
And no need to explain applications of high-dimensional boolean algebra on HN, with boolean algebra you can solve any logic problem expressed as boolean function, any combinatorial problem (except for those with nasty functions), classic graph theory problems.
Surprisingly it allows to solve optimization problems[4], like boolean programming, SAT solver, max independent set or max cut in graphs, very efficiently, it can be used in something like belief propagation or lattice induction for inference, but if that's not enough you can use it for random number generation, lossless compression, perfect hashing, etc, etc.
I haven't seen such a versatile data structure elsewhere, most of the other things developed in the last 35 years, like the ones in the comment below are solving special cases, BDD is truly one of the most fundamental and severely underrated "swiss army knives" (that is in CS, EE people know it very well in logic synthesis and verification, BDD's first "killer app").
It's probably easier to list what you can't do with BDD, kind of like what you can't do with (high-dimensional) boolean logic.
I think it skipped the radar of CompSci community at large because it was too quickly siloed into "that circuit analysis/verification tool used by electrical engineers".
Yes, it's "just" a DAG but with very particular (and very simple) constraints which allow it to solve infinite variety of problems in a very elegant and surprising way [5].
[1] it's really worth watching the lecture on BDDs by Don Knuth , starting around 13:32, his enthusiasm is contagious: https://www.amazon.com/Art-Computer-Programming-Combinatoria...
There is a free preprint here https://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz
[3] https://en.wikipedia.org/wiki/Zero-suppressed_decision_diagr...
[4] Bergman, David, et al. "Discrete optimization with decision diagrams." INFORMS Journal on Computing 28.1 (2016): 47-66.
[5] Bryant, Randal E. "Graph-based algorithms for boolean function manipulation." Computers, IEEE Transactions on 100.8 (1986): 677-691.
I hope that answers your question, dang, and sorry for title mishap.
Vol 4B was partially published in fascicles: https://www.amazon.com/Art-Computer-Programming-Fascicle-Pre... and https://www.amazon.com/Art-Computer-Programming-Fascicle-Sat...
Instead of the ultimate edition of vols 1-3, so far we've got a "patch" by Martin Ruckert who coordinated the volunteers: https://www.amazon.com/MMIX-Supplement-Computer-Programming-...