|Generate QR code
Open Access
Subscription Access
On the complexity of computing the “Shuffled Inequality” function in classical and quantum NOBDDs
https://doi.org/10.26907/0021-3446-2025-1-3-14
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 function “Shuffled Inequality” NEQS is presented, for which a lower and an upper bounds for the complexity of nondeterministic OBDD are proved. The upper bound is an improvement of a previously known result. A quantum measure-many non-deterministic 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.
About the Author
A. F. Gainutdinova
Kazan Federal University
Russian Federation
Russian Federation
Aida F. Gainutdinova.
18 Kremlyovskaya str., Kazan, 420008
References
1. Lee C.Y. Representation of switching circuits by binary-decision programs, Bell Syst. Techn. J. 38 (4), 985-999 (1959).
2. Masek W. A fast algorithm for the string edition problem and decision graph complexity. Master’s thesis (Dep. Electr. Engineer. Comput. Sci. Massachusetts Institute of Techonology, Cambridge, 1976).
3. Кузьмин В. А. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ, Сб. научи, тр. Методы дискр. анализа в теории кодов и схем. 29, 11-39 (1976).
4. Wegener I. Branching programs and binary decision diagrams: theory and applications (Soc. Industr. Appl. Math., Dortmund, 2000).
5. Cobham A. The recognition problem for the set of perfect squares, Proc. 7th Symposium on Switching Automata Theory (SWAT), 78-87 (1966).
6. Pudlak P., Zak S. Space complexity of computations (Univ. Prague, Prague, 1983).
7. Meinel С., Theobald Т. Algorithms and data structures in VLSI design: OBDD-foundations and applications (Springer Science & Business Media, Germany, 1998).
8. Gainutdinova A., Yakaryilmaz A. Nondeterministic unitary OBDDs, Leet. Notes Comp. Sci., 10304, 126-140 (2017).
9. Ablayev F., Gainutdinova A., Khadiev K., Yakaryilmaz A. Very narrow quantum OBDDs and width hierarchies for classical OBDDs, Lobachevskii J. Math. 37 (6), 670-682 (2016).
10. Ablayev F., Gainutdinova A. Complexity of quantum uniform and nonuniform automata, Developments Language Theory 3572, 78-87 (2005).
11. Nielsen Michael A., Chuang Isaac L. Quantum Computation and Quantum Information (Cambridge Univ. Press, 2010).
12. Гайнутдинова А.Ф. Квантовое и классическое моделирование ветвящихся программ, Учен. зап. Ка-занск. ун-та. Сер. физ.-матем. науки 151 (2), 45-58 (2009).
13. Гайнутдинова А.Ф. О моделировании квантовых и классических бинарных программ, Дискр. анализ и исследов. операций. Сер. 1, 13 (1), 45-64 (2006).
14. Ablayev F., Gainutdinova A., Karpinski М. On Computational Power of Quantum Branching Programs, Proc, of the 13th international symposium, Fundament. Comput. Theory (FCT 2001, Riga, Latvia) 2138, 59-70 (2001).
Review
For citations:
Gainutdinova A.F. On the complexity of computing the “Shuffled Inequality” function in classical and quantum NOBDDs. Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika. 2025;(1):3-14. (In Russ.) https://doi.org/10.26907/0021-3446-2025-1-3-14
Views:
49
Email this article 