Том 2, номер 3, 1995 г., Стр. 18-23
УДК 519.71
Н. Ю. Золотых, В. Н. Шевченко
Расшифровка пороговых функций $k$-значной логики
Аннотация:
Рассматривается класс пороговых функций $k$-значной логики от $n$ переменных.
Под расшифровкой функции из этого класса понимается процедура из
последовательности вопросов о значении функции в точке, после завершения
которой функция восстанавливается в остальных точках. Доказано, что при
любом фиксированном $n$ существует алгоритм расшифровки любой пороговой
функции $k$-значной логики, который использует не более $C_n\log^n(k+1)$ вопросов
о значении функции в точке, где $C_n$ – константа, зависящая только от $n$.
Библиогр. 15.
Золотых Н. Ю. 1
Шевченко В. Н. 1
1. Нижегородский государственный университет им. Н. И. Лобачевского,
пр. Гагарина, 23, 603600 Нижний Новгород, Россия
Статья поступила 23 ноября 1994 г.
|