KFU. Card publication. О сложности вычисления функции “Перемешанное неравенство” в классических и квантовых NOBDD

KAZAN
FEDERAL UNIVERSITY

- RUS
- 中文
- ES

О СЛОЖНОСТИ ВЫЧИСЛЕНИЯ ФУНКЦИИ &LDQUO;ПЕРЕМЕШАННОЕ НЕРАВЕНСТВО&RDQUO; В КЛАССИЧЕСКИХ И КВАНТОВЫХ NOBDD

Form of presentation

Articles in Russian journals and collections

Year of publication

2025

Язык

русский

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 NOBDD //Izvestiya vysshikh uchebnykh zavedeniy. Matematika. – 2025. – №. 1. – S. 3-14.

Annotation

В работе исследуются упорядоченные ветвящиеся диаграммы решений (OBDD) -- модель для вычисления булевых функций. Известно, что сложность OBDD может критически зависеть от порядка считывания переменных. Существуют техники построения функций, не позволяющих подобрать оптимальный порядок считывания, одна из которых используется в работе. Рассматривается функция «Перемешанное неравенство» $NEQS$, для которой доказываются нижняя и верхняя оценки сложности недетерминированной OBDD. Верхняя оценка является улучшением известного ранее результата. Строится квантовая много раз измеряющая недетерминированная OBDD, которая является более эффективной, чем классическая. Уточняется иерархия классов сложности, определенных на основе OBDD.

Keywords

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

The name of the journal

Известия ВУЗов, Математика

Please use this ID to quote from or refer to the card

https://repository.kpfu.ru/eng/?p_id=313121&p_lang=2

Full metadata record

Field DC	Value	Language
dc.contributor.author	Gaynutdinova Aida Faritovna	ru_RU
dc.date.accessioned	2025-01-01T00:00:00Z	ru_RU
dc.date.available	2025-01-01T00:00:00Z	ru_RU
dc.date.issued	2025	ru_RU
dc.identifier.citation	Гайнутдинова А. Ф. О сложности вычисления функции “Перемешанное неравенство” в классических и квантовых NOBDD //Известия высших учебных заведений. Математика. – 2025. – №. 1. – С. 3-14.	ru_RU
dc.identifier.uri	https://repository.kpfu.ru/eng/?p_id=313121&p_lang=2	ru_RU
dc.description.abstract	Известия ВУЗов, Математика	ru_RU
dc.description.abstract	В работе исследуются упорядоченные ветвящиеся диаграммы решений (OBDD) -- модель для вычисления булевых функций. Известно, что сложность OBDD может критически зависеть от порядка считывания переменных. Существуют техники построения функций, не позволяющих подобрать оптимальный порядок считывания, одна из которых используется в работе. Рассматривается функция «Перемешанное неравенство» $NEQS$, для которой доказываются нижняя и верхняя оценки сложности недетерминированной OBDD. Верхняя оценка является улучшением известного ранее результата. Строится квантовая много раз измеряющая недетерминированная OBDD, которая является более эффективной, чем классическая. Уточняется иерархия классов сложности, определенных на основе OBDD.	ru_RU
dc.language.iso	ru	ru_RU
dc.subject	Упорядоченная ветвящаяся диаграмма решений	ru_RU
dc.subject	OBDD	ru_RU
dc.subject	сложность	ru_RU
dc.subject	квантовый алгоритм	ru_RU
dc.subject	недетерминизм	ru_RU
dc.subject	класс сложности	ru_RU
dc.title	О сложности вычисления функции “Перемешанное неравенство” в классических и квантовых NOBDD	ru_RU
dc.type	Articles in Russian journals and collections	ru_RU