Form of presentation | Conference proceedings in Russian journals and collections |
Year of publication | 2023 |
Язык | русский |
|
Gaynutdinova Aida Faritovna, author
|
Bibliographic description in the original language |
Gaynutdinova A. F. O slozhnosti vychisleniya funkcii «Peremeshannoe neravenstvo» v klassicheskikh i kvantovykh nedeterminirovannykh OBDD // Diskretnye modeli v teorii upravlyayushhikh sistem : XI Mezhdunarodnaya konferenciya, Moskva i Podmoskove, 26–29 maya 2023 g. : Trudy / Otv. red. S.A. Lozhkin, D.S. Romanov, V.V. Podymov. – M: MAKS Press, 2023. – S. 30-33. |
Annotation |
Дискретные модели в теории управляющих систем : XI Международная конференция, Москва и Подмосковье, 26–29 мая 2023 г. : Труды |
Keywords |
Модели вычислений, сложность вычислений, квантовые алгоритмы, упорядоченные ветвящиеся диаграммы решений |
The name of the journal |
Дискретные модели в теории управляющих систем : XI Международная конференция, Москва и Подмосковье, 26–29 мая 2023 г. : Труды
|
URL |
https://m.cs.msu.ru/s/kQwxWc8jwR68Zn5 |
Please use this ID to quote from or refer to the card |
https://repository.kpfu.ru/eng/?p_id=293564&p_lang=2 |
Full metadata record ![](https://shelly.kpfu.ru/pdf/picture/arrow_black_right.gif) |
Field DC |
Value |
Language |
dc.contributor.author |
Gaynutdinova Aida Faritovna |
ru_RU |
dc.date.accessioned |
2023-01-01T00:00:00Z |
ru_RU |
dc.date.available |
2023-01-01T00:00:00Z |
ru_RU |
dc.date.issued |
2023 |
ru_RU |
dc.identifier.citation |
Гайнутдинова А. Ф. О сложности вычисления функции «Перемешанное неравенство» в классических и квантовых недетерминированных OBDD // Дискретные модели в теории управляющих систем : XI Международная конференция, Москва и Подмосковье, 26–29 мая 2023 г. : Труды / Отв. ред. С.А. Ложкин, Д.С. Романов, В.В. Подымов. – М: МАКС Пресс, 2023. – С. 30-33. |
ru_RU |
dc.identifier.uri |
https://repository.kpfu.ru/eng/?p_id=293564&p_lang=2 |
ru_RU |
dc.description.abstract |
Дискретные модели в теории управляющих систем : XI Международная конференция, Москва и Подмосковье, 26–29 мая 2023 г. : Труды |
ru_RU |
dc.description.abstract |
Ветвящиеся программы (BP – branching programs) – известная модель для представления булевых функций. Упорядоченные ветвящиеся диаграммы решений (OBDD – ordered binary decision diagrams) - это ветвящиеся программы, являющиеся уровневыми, забывающими и один раз считывающими. Модель недетерминированных OBDD допускает недетерминированные переходы при вычислении. Основной мерой сложности OBDD P является ее ширина Width(P). Известно, что сложность OBDD существенным образом зависит от порядка считывания переменных. Так, для функции «Равенство» EQ_2n (NEQ_2n (x,y)= 1 \⇔ x≠ y,x,y∈{0,1}^n) выполняется Width(P) =Ω(2^n) при использовании естественного порядка считывания переменных и Width(P) =3 при использовании наилучшего порядка считывания. Для устранения зависимости сложности от порядка считывания битов входа применяются различные техники построения функций. Для таких функций порядок считывания переменных определяется самим входным набором. В работе рассматривается одна из таких техник. Рассматривается функция «Перемешанное неравенство» NEQS_n. Доказываются нижняя и верхняя оценки ширины недетерминированной OBDD для этой функции. Полученная верхняя оценка является улучшением результата, представленного в работе (Very narrow quantum OBDDs and width hierarchies for classical OBDDs F. Ablayev, A Gainutdinova, K Khadiev, A Yakaryılmaz. - Lobachevskii Journal of Mathematics, 2016). Строится квантовая недетерминированная OBDD для функции NEQS_n, показывается, что квантовая OBDD является более эффективной, чем классическая. |
ru_RU |
dc.language.iso |
ru |
ru_RU |
dc.subject |
Модели вычислений |
ru_RU |
dc.subject |
сложность вычислений |
ru_RU |
dc.subject |
квантовые алгоритмы |
ru_RU |
dc.subject |
упорядоченные ветвящиеся диаграммы решений |
ru_RU |
dc.title |
О сложности вычисления функции «Перемешанное неравенство» в классических и квантовых недетерминированных OBDD |
ru_RU |
dc.type |
Conference proceedings in Russian journals and collections |
ru_RU |
|