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

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

Journal

Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika)
ISSN: 2071-0410 , E-ISSN: 2311-2263

Output data

Year: 2025, Number: 67, Pages: 110-117 Pages count : 8 DOI: 10.17223/20710410/67/6

Funding (1)

Омский филиал ФГБУН «Институт математики им. С.Л. Соболева СО РАН».

FWNF-2022-0003

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

Лопатин А.А. , Рыбалов А.Н.
О генерической сложности решения уравнений над бициклическим моноидом
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2025. №67. С.110-117. DOI: 10.17223/20710410/67/6 WOS РИНЦ OpenAlex

Published print:	Mar 12, 2025
Published online:	Mar 12, 2025

Web of science:	WOS:001483854800007
Elibrary:	80437730
OpenAlex:	W4408924542

Пока нет цитирований