Representations of Boolean functions using restricted types of binary decision diagrams are popular in automated verification. This paper is concerned with reductions among computational problems that are appropriate for these kinds of restricted branching programs, in the sense that, if a problem B (represented by a family of Boolean functions, one for each input size) has a polynomial diagram, and problem A can be reduced to B, then A must also have a polynomial diagram. The notion of “reduction” here must be carefully defined in order to guarantee this and other properties one normally expects from reductions.

In this paper, the authors consider reductions computed by read-once diagrams. They investigate whether the complexity classes consisting of all functions representable by polynomial diagrams (for various restricted types of diagrams) contain problems that are complete with respect to these read-once reductions. The results are that the classes corresponding to ordered binary decision diagrams (OBDDs) and some generalizations of these allowing for a fixed number of layers of OBDDs do have complete problems, but the classes corresponding to tree diagrams and the class corresponding to the read-once diagrams themselves do not have complete problems. The proof of the positive result is inspired by the completeness of the circuit value problem for polynomial time. The proofs of the negative results are combinatorial in character.

This is a technical research paper that will be of interest to theoreticians interested in the complexity-theoretic aspects of binary decision diagrams, used as a restricted computation model. It is one of the first papers to study this aspect.