Abstract:
In this paper we investigate a model of computation of Boolean functions – Ordered Binary Decision Diagrams (OBDD). We consider partial functions and complexity of their computation in different variants of OBDD (deterministic, probabilistic, and quantum). The interested complexity measure is a width of OBDD. It is known that for total functions, bounded-error probabilistic OBDDs can be more effective than the deterministic ones, and this gap cannot be more than exponential. The similar result holds when we compare quantum and deterministic models. In this paper it is shown that for partial functions the gap between quantum and classical, and between probabilistic and deterministic OBDDs can be more than exponential. A partial function is presented which is computed without an error by a quantum OBDD of width 2. Deterministic and bounded-error probabilistic OBDDs for this function must have widths exponentially depending on the parameter of the function. An infinite family of partial functions is also presented such that each function from this family is computed by a bounded-error probabilistic OBDD of width 2. There exists an infinite subset of functions from this family such that a width of a deterministic OBDD for each function from this subset increases indefinitely.
Fulltext:
PDF file (544 kB)