Том 16, номер 5, 2009 г., Стр. 69-77
УДК 519.714.4 + 519.725
Е. А. Окольнишникова
Нижняя оценка сложности вычисления характеристических функций БЧХ-кодов ветвящимися программами
Аннотация:
Получена нижняя оценка$\Omega(n\log n)$ сложности вычисления недетерминированными ветвящимися программами характеристических функций кодов Боуза–Чоудхури–Хоквингема (БЧХ-кодов) при некоторых значениях параметров этих кодов.
Библиогр. 9.
Ключевые слова: сложность, нижняя оценка, ветвящаяся программа, коды.
Окольнишникова Елизавета Антоновна 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 10 августа 2009 г.
