|сгенерировать QR код
Открытый доступ
Только для подписчиков
О сложности вычисления функции “Перемешанное неравенство” в классических и квантовых NOBDD
https://doi.org/10.26907/0021-3446-2025-1-3-14
Аннотация
В работе исследуются упорядоченные ветвящиеся диаграммы решений (OBDD) — модель для вычисления булевых функций. Известно, что сложность OBDD может критически зависеть от порядка считывания переменных. Существуют техники построения функций, не позволяющих подобрать оптимальный порядок считывания, одна из которых используется в работе. Рассматривается функция «Перемешанное неравенство» NEQS, для которой доказываются нижняя и верхняя оценки сложности недетерминированной OBDD. Верхняя оценка является улучшением известного ранее результата. Строится квантовая много раз измеряющая недетерминированная OBDD, которая является более эффективной, чем классическая. Уточняется иерархия классов сложности, определенных на основе OBDD.
Ключевые слова
упорядоченная ветвящаяся диаграмма решений,
OBDD,
сложность,
квантовый алгоритм,
недетерминизм,
класс сложности
При поддержке: Работа выполнена за счет средств Программы стратегического академического лидерства Казанского (Приволжского) федерального университета (“ПРИОРИТЕТ-2030”).
Об авторе
А. Ф. Гайнутдинова
Казанский федеральный университет
Россия
Россия
Гайнутдинова Аида Фаритовна.
ул. Кремлевская, д. 18, Казань, 420008
Список литературы
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).
Рецензия
Для цитирования:
Гайнутдинова А.Ф. О сложности вычисления функции “Перемешанное неравенство” в классических и квантовых NOBDD. Известия высших учебных заведений. Математика. 2025;(1):3-14. https://doi.org/10.26907/0021-3446-2025-1-3-14
For citation:
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
Просмотров:
50
Послать статью по эл. почте 