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

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

Dates:

Submitted:	Oct 15, 2025
Accepted:	Nov 6, 2025
Published print:	May 4, 2026
Published online:	May 4, 2026

Identifiers: No identifiers

Altmetrics: