Бесповторность распознается схемами линейной сложности

В работе рассматривается задача распознавания представимости бесповторными формулами булевых функций, задаваемых вектор-столбцом их значений, при помощи схем из функциональных элементов. Доказана линейная сложность искомой последовательности схем.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 04–01–00359.