Использование запросов существенности для расшифровки бесповторных функций

Булева функция называется бесповторной, если ее можно выразить формулой над базисом $\{\land,\lor,\neg\}$, в которой каждая переменная встречается не более одного раза. Рассматривается задача расшифровки, или идентификации, неизвестной бесповторной функции $f$, зависящей от известного множества переменных $x_1,\dots,x_n$, с помощью запросов. Алгоритмы могут выполнять стандартные запросы принадлежности, а также запросы двух специальных типов, выявляющие существенность переменных у подфункций $f$. Строятся два алгоритма точной идентификации: первый выполняет $O(n^2)$ запросов типа да/нет, второй – $O(n\log^2n)$ запросов с ответами логарифмической длины. Мощностная нижняя оценка числа бит, передаваемых от оракулов к алгоритмам в худшем случае, составляет $\Omega(n\log n)$. Библ. – 14 назв.