|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Реализация булевых функций формулами в непрерывных базисах, содержащих континуум констант
Я. В. Вегнер, С. Б. Гашков Московский государственный университет им. М. В. Ломоносова
Аннотация:
Показано, как для произвольной булевой функции $n$ переменных построить формулы сложности $O(2^{n/2})$ в базисах
$$
\{x-y,xy,|x|\} \cup [0,1],\qquad \{x-y,x*y,2x,|x|\} \cup [0,1],
$$
где ${x*y=\max(-1,\min(1,x))\max(-1,\min(1,y))}$. Данные оценки, вообще говоря, по порядку неулучшаемы.
Библиография: 3 названия.
Поступило: 26.04.2009 Исправленный вариант: 19.12.2010
Образец цитирования:
Я. В. Вегнер, С. Б. Гашков, “Реализация булевых функций формулами в непрерывных базисах, содержащих континуум констант”, Матем. заметки, 92:2 (2012), 181–191; Math. Notes, 92:2 (2012), 166–175
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mzm7833https://doi.org/10.4213/mzm7833 https://www.mathnet.ru/rus/mzm/v92/i2/p181
|
Статистика просмотров: |
Страница аннотации: | 524 | PDF полного текста: | 193 | Список литературы: | 55 | Первая страница: | 12 |
|