О ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ НЕКОТОРЫХ ЗАДАЧ НА ОБОБЩЕННЫХ КЛЕТОЧНЫХ АВТОМАТАХ

П. Г. Ключарев

Аннотация


В статье доказана теорема о NP-трудности задачи восстановления предыдущего состояния обобщенного клеточного автомата. Показано также, что в случае двуместности локальной функции связи эта задача полиномиальна. Полученные в статье результаты представляют ценность для обоснования криптостойкости шифров, основанных на клеточных автоматах.

Ключевые слова


клеточный автомат; NP -полнота

Полный текст:

PDF

Литература


1 Neumann J. von. The general and logical theory of automata // Cerebral mechanisms in behavior. 1951. P. 1—41.

2 Durand B. A random NP-complete problem for inversion of 2D cellular automata // Theoretical computer science. 1995. Vol. 148. № 1. P. 19-32.

3 Krom M. R. The Decision Problem for a Class of First Order Formulas in Which all Disjunctions are Binary // Mathematical Logic Quarterly. 1967. Vol. 13. № 1. P. 15-20.

4 Сухинин Б. М. Исследование характеристик лавинного эффекта в двоичных клеточных автоматах с равновесными функциями переходов // Наука и образование: электронное научно-техническое издание. 2010. № 8. URL: http://technomag.edu.ru/ doc/159565.html.

5 Сухинин Б. М. Разработка генераторов псевдослучайных двоичных последовательностей на основе клеточных автоматов // Наука и образование: электронное научно-техническое издание. 2010. № 9. URL: http://technomag.edu.ru/doc/159714.html.

6 Ключарев П. Г. Клеточные автоматы, основанные на графах Рамануджана, в задачах генерации псевдослучайных последовательностей // Наука и образование. Электронное научно-техническое издание. 2011. № 10. URL: http://technomag. edu.ru/doc/241308.html.


Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.