Том 7, серия 1, номер 1, 2000 г., Стр. 67-78
УДК 519.714
Р. Г. Мубаракзянов
О классах сложности, определяемых бинарными программами ограниченной ширины
Аннотация:
Рассматриваются классы сложности, образованные булевыми функциями, реализуемыми полиномиальными один раз читающими упорядоченными бинарными программами (OBDD в англоязычной литературе). Соотношения между классами, определяемыми вероятностными, детерминированными и недетерминированными OBDD, были доказаны ранее. В статье доказаны все соотношения между классами сложности, возникающими при рассмотрении OBDD, ширина которых ограничена константой, а также в том случае, когда связи между слоями фиксированы. Кроме того, определена функция, вычислимая полиномиальной вероятностной OBDD, ширина которой ограничена константой и связи между слоями фиксированы. Эта функция не принадлежит классам BPP, NP, coNP в контексте OBDD.
Библиогр. 8.
Мубаракзянов Р. Г. 1
1. Казанский государственный университет,
ул. Кремлевская, 18, 420008 Казань, Россия
е-mail: rustam@ksu.ru
Статья поступила 7 декабря 1999 г.
