|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях)
О сложности расшифровки разбиения булева куба на подкубы
В. В. Осокин
Аннотация:
Рассматривается известная задача расшифровки функций алгебры логики, то есть задача восстановления значений функции на всех наборах $n$-мерного булева куба по известным значениям на некоторых из этих наборов. В общем случае для определения функции нужно знать ее значения на всех $2^n$ наборах. Но если функция принадлежит некоторому более узкому классу, чем класс всех функций алгебры
логики от $n$ переменных, то для ее определения могут потребоваться лишь значения на некотором подмножестве $n$-мерного булева куба. В данной работе рассматриваются классы функций, производящих разбиение $n$-мерного булева куба на подкубы. Получены асимптотические оценки сложности расшифровки функций из таких классов.
Статья поступила: 10.07.2006
Образец цитирования:
В. В. Осокин, “О сложности расшифровки разбиения булева куба на подкубы”, Дискрет. матем., 20:2 (2008), 46–62; Discrete Math. Appl., 18:2 (2008), 155–172
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1003https://doi.org/10.4213/dm1003 https://www.mathnet.ru/rus/dm/v20/i2/p46
|
Статистика просмотров: |
Страница аннотации: | 664 | PDF полного текста: | 280 | Список литературы: | 70 | Первая страница: | 15 |
|