Tree Decision Diagrams Emerge as a More Efficient Alternative to OBDD

This paper introduces Tree Decision Diagrams (TDD), a generalization of the classical OBDD model for representing Boolean functions with significantly improved efficiency and expressiveness. Unlike OBDD, TDD can tractably represent CNF formulas with bounded treewidth—a fundamental capability that has remained impossible for decades. The advancement has major implications for SAT solvers, formal verification systems, and knowledge compilation applications that depend on efficient handling of complex logical constraints.