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

КАЗАНСКИЙ
ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ

RUS

- EN
- 中文
- ES

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

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

Статьи в российских журналах и сборниках

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

2025

Язык

русский

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

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

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

Гайнутдинова А. Ф. О сложности вычисления функции “Перемешанное неравенство” в классических и квантовых NOBDD //Известия высших учебных заведений. Математика. – 2025. – №. 1. – С. 3-14.

Аннотация

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

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

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

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

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

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

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

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

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