Изучается генерическая сложность двух вариантов проблемы решения уравнений без констант над конечными предикатными алгебраическими системами: распознавания разрешимости и поиска решения. Для обеих проблем во многих случаях неизвестно эффективных полиномиальных алгоритмов. Предлагается полиномиальный генерический алгоритм для проблемы распознавания разрешимости. С другой стороны, для проблемы поиска решения доказывается, что если для нее нет полиномиального вероятностного алгоритма, то существует подпроблема этой проблемы, для которой нет полиномиального генерического алгоритма. Полученный результат является теоретическим обоснованием возможных приложений проблемы поиска решения в криптографии, где нужно, чтобы проблема взлома криптоалгоритма была трудной для почти всех входов.
1 Visitors
1 Hits
0 Downloads
