О сложности полиномиальных возвратных последовательностей

Рассмотрены возвратные последовательности над множеством целых чисел, у которых в качестве порождающих функций используются произвольные суперпозиции полиномиальных функций и функции sg, – полиномиальные возвратные последовательности. Определены полиномиально-регистровые машины (PR-машины), близкие к машинам с произвольным доступом к памяти. Доказано, что вычисления на PR-машинах можно промоделировать полиномиальными возвратными последовательностями. С другой стороны, вычисление элементов полиномиальной возвратной последовательности можно выполнить с помощью подходящей PR-машины.

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

Источник финансирования

Работа выполнена при частичной финансовой поддержке Российского фонда фундаментальных исследований (номер проекта 16-01-00593)

Получено

12.10.2018

Дата публикации

12.10.2018

Кол-во символов

601

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Марченков С. С. О сложности полиномиальных возвратных последовательностей // Проблемы передачи информации – 2018. – Tом 54. – Выпуск 3 C. 67-72 [Электронный ресурс]. URL: http://ras.jes.su/ppi/s207987840000560-5-1 (дата обращения: 04.05.2024). DOI: 10.31857/S055529230001315-0
MLA	Marchenkov, S. "On the Complexity of Polynomial Recurrence Sequences." Problemy peredachi informatsii 54.3 (2018):67-72. DOI: 10.31857/S055529230001315-0
APA	Marchenkov S. (2018). On the Complexity of Polynomial Recurrence Sequences. Problemy peredachi informatsii 54(3), pp.67-72 DOI: 10.31857/S055529230001315-0

Размещенный ниже текст является ознакомительной версией и может не соответствовать печатной.

всего просмотров: 982

Оценка читателей: голосов 0

1. Холл М. Комбинаторика. М.: Мир, 1970.

2. Нечаев В.И. Элементы криптографии: Основы теории защиты информации. М.: Высш. шк., 1999.

3. Марченков С.С. О сложности возвратных последовательностей // Дискрет. матем. 2003. Т. 15. № 2. С. 52–62.

4. Минский М. Вычисления и автоматы. М.: Мир, 1971.

5. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.