"Записки научных семинаров ПОМИ"
Том 402, стр. 91-107
Полная односторонняя функция,
основанная на свободном $\mathbb Z\times \mathbb Z$-модуле конечного ранга
С. И. Николенко, Д. С. Тугарёв
С.-Петербургское отделение
Математического института
им. В. А. Стеклова РАН,
Фонтанка 27, 191023 Санкт-Петербург,
Академический Университет РАН,
Россия
sergey@logic.pdmi.ras.ru
Академический Университет РАН, Санкт-Петербург,
Россия
tugaryov@mail.ru
- Аннотация: Известно, что задача принадлежности подполумодулю для свободного
$\mathbb Z\times\mathbb Z$-модуля конечного ранга неразрешима. Модифицируя конструкцию
неразрешимости, мы строим комбинаторную полную одностороннюю функцию,
основанную на свободном $\mathbb Z\times\mathbb Z$-модуле конечного ранга.
Библ. -- 23 назв.
- Ключевые слова: односторонние функции, сложность в среднем, задачи замощения
[one-way functions, average-case complexity, tiling problems]
Полный текст(.pdf)