A simpler counterexample to a long-standing conjecture on the complexity of Bryantʼs apply algorithm

•Bryant (1986) introduced OBDDs as a data structure for Boolean functions.•Synthesis is a key operation for the manipulation of Boolean functions.•Bryant conjectured that his apply procedure for synthesis works in linear time with respect to input and output size.•Yoshinaka et al. (2012) presented a counterexample which works for a bad variable ordering.•Here we present a simpler counterexample that works for very good variable orderings.

In 1986 in his seminal paper Bryant has introduced Ordered Binary Decision Diagrams (OBDDs) as a dynamic data structure for the representation and manipulation of Boolean functions which allow efficient algorithms for important operations like synthesis, the combination of two Boolean functions by a Boolean operator, and equivalence checking. Based on his empirical evaluation he has conjectured that his apply algorithm for the synthesis works in linear time with respect to the input and output size. Recently in 2012, Yoshinaka et al. have presented a counterexample which contradicts this conjecture but their example has the drawback that the chosen variable ordering for the OBDD representation of the input and output is bad. Therefore, they have raised the question whether Bryantʼs conjecture may still stand for reasonable variable orderings. Here, a negative answer is given by presenting a simple counterexample which works for such kind of variable orderings.