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

Квантовые и классические недетерминированные OBDD

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

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

Аннотация: Исследована модель недетерминированных упорядоченных ветвящихся диаграмм решений (NOBDD). Дан метод доказательства нижней оценки сложности квантовой NOBDD. Представлены функция, имеющая линейную сложность в квантовой NOBDD и константную сложность в классической NOBDD, а также функция, имеющая одинаковую сложность в квантовой и классической моделях. Описано соотношение сложностных классов, определенных для модели OBDD.

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

УДК: 519.71

Поступила в редакцию: 05.07.2024
Принята в печать: 10.10.2024

DOI: 10.26907/2541-7746.2024.4.470-484