Сложность ветвящихся программ для частично определенных функций

Упорядоченные ветвящиеся диаграммы решений (OBDD – Ordered Binary Decision Diagrams) – известная модель для вычисления булевых функций. В работе рассмотрены частично определенные булевы функции и сложность их вычисления в различных вариантах OBDD (детерминированных, недетерминированных, вероятностных и квантовых). В качестве исследуемой меры сложности взята ширина OBDD. Известно, что при рассмотрении всюду определенных булевых функций вероятностные OBDD могут быть эффективнее детерминированных и данный разрыв в сложности может быть не более чем экспоненциальным. Аналогичный результат верен и при сравнении квантовых OBDD с классическими. Показано, что для частично определенных функций преимущество в сложности квантовых моделей перед классическими может быть усилено. Предложена частично определенная булева функция, которая вычислима с нулевой ошибкой квантовой OBDD ширины 2. При этом ширина классических детерминированной, вероятностной OBDD экспоненциально зависит от параметра функции. Предложено также бесконечное семейство частично определенных булевых функций таких, что любая функция из данного семейства вычислима с ограниченной ошибкой вероятностной OBDD ширины 2. При этом существует бесконечное подмножество функций из данного семейства таких, что ширина классической детерминированной OBDD для вычисления каждой функции из данного подмножества возрастает неограниченно.