Том 3, номер 1, 1996 г., Стр. 52-56
УДК 519.714
Ю. В. Мерекин
Нижняя оценка сложности для схем конкатенации слов
Аннотация:
Приводится метод получения нижних оценок сложности для схем конкатенации слов. В частности, для последовательности де Брейна получена нижняя оценка вида$l/\log_2l$ , где$l$ – длина слова. Доказывается, что сложность линейной булевой функции$k$ переменных в этом классе схем равна$2k-1$ .
Ил. 1, библиогр. 12.
Мерекин Ю. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 5 января 1996 г.
