EN
О максимально сложно реализуемых отображениях
Получена: 28.04.2026 Доработана: 26.06.2026 Принята: 13.07.2026
Опубликована: 2026 год, том 30, выпуск 3, С. 126–140
Аннотация
Данная работа продолжает изучение вопроса сложности реализуемости автоматов посредством кодирований алфавита состояний. Ранее изучался вопрос простой реализуемости как автоматов, так и отображений на конечном множестве. В данной работе изучаются сложно реализуемые отображения на конечном множестве, т. е. такие отображения, что любое неизбыточное кодирование приводит к булеву оператору максимальной сложности с точки зрения степени полинома Жегалкина. Доказано, что для любой мощности множества \(n=2^k\) существуют сложно реализуемые отображения. Существование таких отображений позволит в дальнейшем доказать существование сложно реализуемых автоматов.
Ключевые слова: теория автоматов, переходные системы, подстановка, кодирование, сложность, булев оператор.
BibTeX
@article{IS-Rodin2026,
author = {Родин, Сергей Борисович},
title = {{О максимально сложно реализуемых отображениях}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {3},
pages = {126--140},
}
AMSBIB
\RBibitem{IS-Rodin2026}
\by С.\,Б.~Родин
\paper О максимально сложно реализуемых отображениях
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 3
\pages 126--140