RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ПОМИ, 2012, том 402, страницы 91–107 (Mi znsl5240)

Полная односторонняя функция, основанная на свободном $\mathbb Z\times\mathbb Z$-модуле конечного ранга

С. И. Николенкоab, Д. С. Тугарёвa

a Академический Университет РАН, Санкт-Петербург, Россия
b С.-Петербургское отделение Математического института им. В. А. Стеклова РАН, Санкт-Петербург, Россия

Аннотация: Известно, что задача принадлежности подполумодулю для свободного $\mathbb Z\times\mathbb Z$-модуля конечного ранга неразрешима. Модифицируя конструкцию неразрешимости, мы строим комбинаторную полную одностороннюю функцию, основанную на свободном $\mathbb Z\times\mathbb Z$-модуле конечного ранга. Библ. – 23 назв.

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

УДК: 510.53

Поступило: 16.05.2012


 Англоязычная версия: Journal of Mathematical Sciences (New York), 2013, 192:3, 307–315

Реферативные базы данных:


© МИАН, 2024