Complexity of branching programs for partial functions

A. F. Gainutdinova

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

Résumé

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.

Détail

Keywords: Ordered Binary Decision Diagrams, partial functions, quantum computation, probabilistic OBDDs, deterministic OBDDs, complexity.

Bibliographie

[1] Sholomov L. A., Osnovy teorii diskretnykh logicheskikh i vychislitelnykh ustroistv, Nauka, M., 1980, 400 pp. | Zbl

[2] Rabin M., “Veroyatnostnye avtomaty”, Kiberneticheskii sb., 9, Mir, M., 1964, 123–141

[3] Freivald R. V., “Ob uvelichenii chisla sostoyanii pri determinizatsii konechnykh veroyatnostnykh avtomatov”, Avtomatika i vychisl. tekhnika, 1982, no. 3, 39–42 | MR

[4] Ablayev F., Karpinski M., “On the power of randomized branching programs”, Proc. ICALP' 96, LNCS, 1099, Springer, 1996, 348–356 | MR | Zbl

[5] Manin Yu. I., Vychislimoe i nevychislimoe, Sov. radio, M., 1980, 128 pp. | MR

[6] Feynman R., “Simulating physics with computers”, Int. J. Theor. Phys., 21:6–7 (1982), 467–488 | DOI | MR

[7] Nielsen M. A., Chuang I. L., Quantum Computation and Quantum Information, Cambridge Univ. Press, Cambridge, 2000, 700 pp. | MR | Zbl

[8] Shor P., “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM J. Sci. Statist. Comput., 26:5 (1997), 1484–1509 | DOI | MR | Zbl

[9] Grover L., “A fast quantum mechanical algorithm for database search”, Proc. STOC' 96, ACM New York, N.Y., 1996, 212–219 | DOI | MR | Zbl

[10] Goldreich O., “On promise problem: A survey”, Shimon Even Festschrift, LNCS, 3895, eds. Goldreich O., Rosenberg A. L., Selman A. L., 2006, 254–290 | MR

[11] Ambainis A., Yakaryılmaz A., “Superiority of exact quantum automata for promise problems”, Inf. Process. Lett., 112:7 (2012), 289–291 | DOI | MR | Zbl

[12] Wegener I., Branching Programs and Binary Decision Diagrams, SIAM, 2000, 411 pp. | MR | Zbl

[13] Lee C. Y., “Representation of switching circuits by binary-decision programs”, Bell Syst. Tech. J., 38:4 (1959), 985–999 | DOI | MR

[14] Akers S. B., “Binary decision diagrams”, IEEE Trans. Comput., C-27:6 (1978), 509–516 | DOI

[15] Kuzmin V. A., “Otsenka slozhnosti realizatsii funktsii algebry logiki prosteishimi vidami binarnykh programm”, Metody diskretnogo analiza v teorii kodov i skhem, 29, In-t matematiki SO AN SSSR, Novosibirsk, 1976, 11–39 | MR

[16] Mazek W., A fast algorithm for the string editing problem and decision graph complexity, Master's Thesis, Massachusetts Institute of Techonology, 1976

[17] Cobham A., “The recognition problem for the set of perfect squares”, Proc. 7th Symposium on Switching and Automata Theory (SWAT), 1996, 78–87

[18] Pudlák P., Zak S., Space complexity of computations, Tech. Report, Math. Inst., CSAV, Prague, 1983, 30 pp.

[19] Pudlák P. A., “A Lower Bound on Complexity of Branching Program”, Proc. of the Mathematical Foundations of Computer Science, Springer-Verlag, 1984, 480–489 | MR

[20] Ablayev F., “Randomization and nondeterminism are incomparable for polynomial ordered binary decision diagrams”, Proc. of the 24th Int. Coll. on Automata, Languages, and Programming (ICALP), LNCS, 1256, 1997, 195–202 | MR

[21] Ablayev F., Karpinski M., A lower bound for integer multiplication on randomized read-once branching programs, Electronic Colloquium on Computational Complexity, Report No 11, URL: , 1998, svobodnyi http://eccc.hpi-web.de/report/1998/011/

[22] Ablayev F., Gainutdinova A., Karpinski M., “On Computational Power of Quantum Branching Programs”, Proc. 13th Int. Symposium “Fundamentals of computation theory” (FCT 2001), LNCS, 2138, Riga, Latvia, 2001, 59–70 | MR | Zbl

[23] Barrington D., “Vetvyaschiesya programmy ogranichennoi shiriny, imeyuschie polinomialnuyu slozhnost, raspoznayut v tochnosti yazyki iz $NC^1$”, Kiberneticheskii sb., 28, Mir, M., 1991, 94–113

[24] Nakanishi M., Hamaguchi K., Kashiwabara T., “Ordered quantum branching programs are more powerful than ordered probabilistic branching programs under a bounded-width restriction”, Proc. 6th Annual Int. Conf. on Computing and Combinatorics (COCOON' 2000), LNCS, 1858, Springer-Verlag, 2000, 467–476 | MR | Zbl

[25] Sauerhoff M., Sieling D., “Quantum branching programs and space-bounded nonuniform quantum complexity”, Theor. Comp. Sci., 334:1–3 (2005), 177–225 | DOI | MR | Zbl

[26] Gainutdinova A. F., “O sravnitelnoi slozhnosti kvantovykh i klassicheskikh binarnykh programm”, Diskretnaya matem., 14:3 (2002), 109–121 | DOI | MR | Zbl

[27] Geffert V., Yakaryılmaz A., “Classical automata on promise problems”, Descriptional Complexity of Formal Systems, Proc. 16th Int. Workshop (DCFS 2014), LNCS, 8614, 2014, 126–137 | Zbl

[28] Ablayev F., Gainutdinova A., Karpinski M., Moore C., Pollette C., “On the computational power of probabilistic and quantum branching program”, Information and Computation, 203:2 (2005), 145–162 | DOI | MR | Zbl

[29] Kemeny J. G., Snell J. L., Finite Markov Chains, D. Van Nostrand Comp. Inc., 1960, 210 pp. | MR | Zbl

[30] Nechiporuk E. I., “Ob odnoi bulevskoi funktsii”, Dokl. AN SSSR, 169:4 (1966), 765–766 | MR | Zbl

[31] Yao A. C., “Some Complexity Questions Related to Distributed Computing”, Proc. 11th STOC, v. 14, 1979, 209–213

[32] Wegener I., “Communication Complexity and BDD Lower Bound Techniques”, Numbers, Information and Complexity, Springer-Verlag, 2000, 615–628 | DOI | MR