О классах сложности, определяемых бинарными программами ограниченной ширины

Рассматриваются классы сложности, образованные булевыми функциями, реализуемыми полиномиальными один раз читающими упорядоченными бинарными программами (OBDD в англоязычной литературе). Соотношения между классами, определяемыми вероятностными, детерминированными и недетерминированными OBDD, были доказаны ранее. В статье доказаны все соотношения между классами сложности, возникающими при рассмотрении OBDD, ширина которых ограничена константой, а также в том случае, когда связи между слоями фиксированы. Кроме того, определена функция, вычислимая полиномиальной вероятностной OBDD, ширина которой ограничена константой и связи между слоями фиксированы. Эта функция не принадлежит классам BPP, NP, coNP в контексте OBDD. Библиогр. 8.