"Записки научных семинаров ПОМИ"
Том 402, стр. 183-217
Использование запросов существенности для
расшифровки бесповторных функций
Д. В. Чистиков
Факультет ВМК,
МГУ имени М. В. Ломоносова,
Ленинские горы,
Москва 119991 ГСП-1, Россия
dch@cs.msu.ru
- Аннотация: Булева функция называется бесповторной, если ее можно выразить
формулой над базисом $\{\land, \lor, \neg\}$, в которой каждая
переменная встречается не более одного раза.
Рассматривается задача расшифровки, или идентификации,
неизвестной бесповторной функции $f$, зависящей от известного
множества переменных $x_1, \ldots, x_n$, с помощью запросов.
Алгоритмы могут выполнять стандартные запросы принадлежности,
а также запросы двух специальных типов, выявляющие существенность
переменных у подфункций $f$.
Строятся два алгоритма точной идентификации: первый выполняет
$O(n^2)$ запросов типа да/нет, второй --- $O(n \log^2 n)$
запросов с ответами логарифмической длины.
Мощностная нижняя оценка числа бит, передаваемых от оракулов
к алгоритмам в худшем случае, составляет $\MyOmega(n \log n)$.
Библ. -- 14 назв.
- Ключевые слова: обучение посредством запросов, расшифровка, точная идентификация,
бесповторная булева функция, существенная переменная
[query learning, exact identification, read-once Boolean function,
relevant variable]
Полный текст(.pdf)