On the Complexity of Computing the Shuffled Inequality Function in Classical and Quantum NOBDDs

Abstract We investigate ordered binary decision diagrams (OBDDs)—a model for computing Boolean functions. It is known that OBDD’s complexity can extremely depend on the order of reading variables. There are techniques for constructing functions that do not allow choosing the optimal order for reading the input, one of which we use in this paper. A shuffled inequality NEQS function is presented, for which a lower bound and an upper bound for the complexity of nondeterministic OBDDs are proved. The upper bound is an improvement of a previously known result. A quantum measure-many nondeterministic OBDD is constructed that is more efficient than the classical one. The hierarchy of complexity classes defined on the basis of OBDD models is clarified.