RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Известия Иркутского государственного университета. Серия Математика:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Известия Иркутского государственного университета. Серия Математика, 2016, том 16, страницы 19–29 (Mi iigum258)  

Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)

Нижняя оценка сложности функций над конечным полем порядка 4 в классе поляризованных полиномов

А. С. Балюк, А. С. Зинченко

Иркутский государственный университет

Аннотация: Представления функций над конечными полями, в том числе полиномиальные, в настоящее время активно исследуются. Одним из основных направлений этих исследований является сложность таких представлений. Вопросы полиномиальных представлений булевых функций довольно хорошо изучены. Для многих классов полиномов найдены точные значения сложности таких представлений.
В последнее время возрос интерес к полиномиальным представлениям функций над конечными полями порядка больше двух и кольцами вычетов по составному модулю. Исследование сложности таких представлений сопряжено с определенными трудностями, и даже в довольно простых классах полиномиальных форм найдены только несовпадающие верхние и нижние оценки сложности.
В настоящей работе внимание уделено поляризованным полиномам над конечным полем порядка 4. Полиномы этого класса представляют собой суммы произведений множителей определенного вида. Каждый полином реализует некоторую $n$-местную функцию над конечным полем. Под сложностью полинома понимается число ненулевых слагаемых в нем. Каждая функция может быть реализована несколькими различными полиномами из одного класса. Под сложностью функции в классе полиномов понимается минимально возможная сложность реализующего ее полинома из этого класса.
Ранее были известны эффективные нижние оценки сложности в классе поляризованных полиномов для случая булевых и трехзначных функций и более слабая мощностная оценка для случая функций над конечным полем простого порядка.
В настоящей статье получена эффективная нижняя оценка сложности функций над конечным полем порядка 4, аналогичная ранее известным оценкам для булевых и трехзначных функций.

Ключевые слова: конечное поле, поляризованный полином, кронекерова форма, нижняя оценка сложности.

Полный текст: PDF файл (278 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 519.714.4
MSC: 68Q17

Образец цитирования: А. С. Балюк, А. С. Зинченко, “Нижняя оценка сложности функций над конечным полем порядка 4 в классе поляризованных полиномов”, Известия Иркутского государственного университета. Серия Математика, 16 (2016), 19–29

Цитирование в формате AMSBIB
\RBibitem{BalZin16}
\by А.~С.~Балюк, А.~С.~Зинченко
\paper Нижняя оценка сложности функций над конечным полем порядка~4 в~классе поляризованных полиномов
\jour Известия Иркутского государственного университета. Серия Математика
\yr 2016
\vol 16
\pages 19--29
\mathnet{http://mi.mathnet.ru/iigum258}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/iigum258
  • http://mi.mathnet.ru/rus/iigum/v16/p19

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. С. Казимиров, С. Ю. Реймеров, “Верхние оценки сложности функций над непростыми конечными полями в классе поляризованных полиномов”, Известия Иркутского государственного университета. Серия Математика, 17 (2016), 378–45  mathnet
    2. А. С. Балюк, А. С. Зинченко, “Нижняя оценка сложности поляризованных полиномов семизначных функций”, Известия Иркутского государственного университета. Серия Математика, 22 (2017), 18–30  mathnet  crossref
  • Просмотров:
    Эта страница:79
    Полный текст:23
    Литература:13
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019