Geodesic
Complexity of branching programs for partial functions
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 3, pp. 30-48

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

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.
Keywords: Ordered Binary Decision Diagrams, partial functions, quantum computation, probabilistic OBDDs, deterministic OBDDs, complexity. 
@article{UZKU_2014_156_3_a3,
     author = {A. F. Gainutdinova},
     title = {Complexity of branching programs for partial functions},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {30--48},
     publisher = {mathdoc},
     volume = {156},
     number = {3},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a3/}
}
TY  - JOUR
AU  - A. F. Gainutdinova
TI  - Complexity of branching programs for partial functions
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2014
SP  - 30
EP  - 48
VL  - 156
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a3/
LA  - ru
ID  - UZKU_2014_156_3_a3
ER  - 
%0 Journal Article
%A A. F. Gainutdinova
%T Complexity of branching programs for partial functions
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2014
%P 30-48
%V 156
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a3/
%G ru
%F UZKU_2014_156_3_a3
A. F. Gainutdinova. Complexity of branching programs for partial functions. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 156 (2014) no. 3, pp. 30-48. http://geodesic.mathdoc.fr/item/UZKU_2014_156_3_a3/