О генерической сложности решения уравнений над бициклическим моноидом

doi:10.17223/20710410/67/6

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О генерической сложности решения уравнений над бициклическим моноидом	662 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/67/6

#генерическая сложность

#NP-полнота

#бициклические моноиды

Title: О генерической сложности решения уравнений над бициклическим моноидом
Creator: Лопатин, Артем Анатольевич
|
Рыбалов, Александр Николаевич
Date: 2025
DOI: 10.17223/20710410/67/6
Description: Изучается вычислительная сложность проблемы проверки разрешимости систем уравнений над бициклическим моноидом. Этот моноид, помимо теоретического значения в топологии и теории полугрупп, имеет приложения в информатике и языках программирования, например как модель для языка Дика сбалансированных скобочных выражений. Доказывается NP-полнота проблемы проверки разрешимости систем уравнений над бициклическим моноидом. Также доказывается, что при P ≠ NP и P = BPP для этой проблемы не существует сильно генерического полиномиального алгоритма. Это означает, что для любого генерического полиномиального алгоритма имеется эффективный метод случайной генерации входов, на которых этот алгоритм не может решить рассматриваемую проблему. Полученный результат указывает на возможное применение данной проблемы в криптографии, где нужно, чтобы проблема взлома криптосистемы была трудной для почти всех входов.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. 2025. № 67. С. 110-117
Language: rus

Created: 20-03-2025

255 Visitors

204 Hits

58 Downloads

Журналы ТГУ О генерической сложности решения уравнений над бициклическим моноидом