Эта публикация цитируется в 1 статье

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

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

Казанский федеральный университет, ул. Кремлевская, д. 18, г. Казань, 420008, Россия

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

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

УДК: 519.71

Поступила: 21.01.2024
Исправленный вариант: 07.03.2024
Принята к публикации: 20.03.2024

DOI: 10.26907/0021-3446-2025-1-3-14

 Англоязычная версия: Russian Mathematics (Izvestiya VUZ. Matematika), 2025, 69:1, 1–10