КФУ. Карточка публикации. О сложности вычисления функции «Перемешанное неравенство» в классических и квантовых недетерминированных OBDD

RUS

- EN
- 中文
- ES

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

Форма представления

Тезисы и материалы конференций в российских журналах и сборниках

Год публикации

2023

Язык

русский

Авторы, сотрудники КФУ

Гайнутдинова Аида Фаритовна, автор

Библиографическое описание на языке оригинала

Гайнутдинова А. Ф. О сложности вычисления функции «Перемешанное неравенство» в классических и квантовых недетерминированных OBDD // Дискретные модели в теории управляющих систем : XI Международная конференция, Москва и Подмосковье, 26–29 мая 2023 г. : Труды / Отв. ред. С.А. Ложкин, Д.С. Романов, В.В. Подымов. – М: МАКС Пресс, 2023. – С. 30-33.

Аннотация

Дискретные модели в теории управляющих систем : XI Международная конференция, Москва и Подмосковье, 26–29 мая 2023 г. : Труды

Ключевые слова

Модели вычислений, сложность вычислений, квантовые алгоритмы, упорядоченные ветвящиеся диаграммы решений

Название журнала

URL

https://m.cs.msu.ru/s/kQwxWc8jwR68Zn5

Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на эту карточку

https://repository.kpfu.ru/?p_id=293564

Полная запись метаданных

Поле DC	Значение	Язык
dc.contributor.author	Гайнутдинова Аида Фаритовна	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/?p_id=293564	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	Тезисы и материалы конференций в российских журналах и сборниках	ru_RU