Реферат: Исследуется проблема совместности систем уравнений над группами с позиций генерической сложности. Генерический подход, который оценивает сложность задачи для «почти всех» входных данных, является эффективным инструментом анализа сложности проблемы, в том числе в криптографии. Основным результатом работы является доказательство существования полиномиального генерического алгоритма, решающего проблему совместности сколемовских систем уравнений для конечных и счётных групп. Этот вывод контрастирует с ранее известными результатами об NP-полноте проблемы распознавания совместности сколемовских систем уравнений над неабелевыми конечными группами (при условии P=BPP и P̸=NP). Полученный результат свидетельствует о ненадёжности использования проблемы распознавания совместности сколемовских систем уравнений в качестве основы для криптографических протоколов. В то же время предложенный алгоритм может быть полезен для требующего массовых вычислений быстрого отбора потенциально разрешимых систем в приложениях.

Библиографическая ссылка: Бучинский И.М. , Трейер А.В.
Генерическая полиномиальная разрешимость проблемы совместности систем уравнений над группами
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2026. №72. С.92-102. DOI: 10.17223/20710410/72/7

Даты:

Поступила в редакцию:	15 окт. 2025 г.
Принята к публикации:	6 нояб. 2025 г.
Опубликована в печати:	4 мая 2026 г.
Опубликована online:	4 мая 2026 г.

Идентификаторы БД: Нет идентификаторов

Альметрики: