KFU. Card publication. О сложности вычисления функции «Перемешанное неравенство» в классических и квантовых недетерминированных OBDD

- RUS
- 中文
- ES

О СЛОЖНОСТИ ВЫЧИСЛЕНИЯ ФУНКЦИИ &LAQUO;ПЕРЕМЕШАННОЕ НЕРАВЕНСТВО&RAQUO; В КЛАССИЧЕСКИХ И КВАНТОВЫХ НЕДЕТЕРМИНИРОВАННЫХ OBDD

Form of presentation

Conference proceedings in Russian journals and collections

Year of publication

2023

Язык

русский

Authors, employees of KFU

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

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

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