Изучается генерическая сложность двух вариантов проблемы решения уравнений без констант над конечными предикатными алгебраическими системами: распознавания разрешимости и поиска решения. Для обеих проблем во многих случаях неизвестно эффективных полиномиальных алгоритмов. Предлагается полиномиальный генерический алгоритм для проблемы распознавания разрешимости. С другой стороны, для проблемы поиска решения доказывается, что если для неё нет полиномиального вероятностного алгоритма, то существует подпроблема этой проблемы, для которой нет полиномиального генерического алгоритма. Полученный результат является теоретическим обоснованием возможных приложений проблемы поиска решения в криптографии, где нужно, чтобы проблема взлома криптоалгоритма была трудной для почти всех входов.
- Title О генерической сложности решения уравнений в конечных предикатных алгебраических системах
- Headline О генерической сложности решения уравнений в конечных предикатных алгебраических системах
- Publesher
Tomsk State University - Issue Прикладная дискретная математика 70
- Date:
- DOI 10.17223/20710410/70/6
Ключевые слова
генерическая сложность, конечные алгебраические системы, уравненияАвторы
Ссылки
Baumslag G., Myasnikov A., and Remeslennikov V. Algebraic geometry over groups I. Algebraic sets and ideal theory // J. Algebra. 1999. V. 219. No. 1. P. 16-79.
Shevlyakov A. N. Equationallv Noetherian varieties of semigroups and B. Plotkin’s problem // Сиб. электрон, матем. изв. 2023. Т. 20. №2. С. 724-734.
Шевляков А. Н. Сплетения полугрупп и проблема Б. И. Плоткина // Алгебра и логика. 2023. Т. 62. №5. С. 665-691.
Shevlyakov А. N. On disjunctions of algebraic sets in completely simple semigroups // Communications in Algebra. 2017. V. 45. No. 9. P.3757-3767.
Шевляков A. H. Об объединении решений систем уравнений в полугруппах с конечным идеалом j j Алгебра и логика. 2016. Т.55. №1. С. 87-105.
Рыболов А. Н. О сложности решения уравнений над графами // Сиб. электрон, матем. изв. 2024. Т. 21. № 1. С. 62-69.
Nikitin A. and Shevlyakov A. On radicals over strict partial order sets // J. Phvs.: Conf. Ser. 2021. V. 1791. No. 012080. 6p.
Goldmann M. and Russell A. The complexity of solving equations over finite groups // Information and Computation. 2002. V. 178. No. 1. P.253-262.
Klima O., Tesson P., and Therien D. Dichotomies in the complexity of solving systems of equations over finite semigroups // Theory Comput. Svst. 2007. V.40. P.263-297.
Ильев А. В., Ильев В. Pd. Алгоритмы для решения систем уравнений над различными классами конечных графов j j Прикладная дискретная математика. 2021. №53. С. 89102.
Kapovich L, Miasnikov A., Schupp Р., and Shpilrain V. Generic-case complexity, decision problems in group theory and random walks // J. Algebra. 2003. V. 264. No. 2. P.665-694.
Rybalov A. and Shevlyakov A. Generic complexity of solving of equations in finite groups, semigroups and fields // J. Phvs.: Conf. Ser. 2021. V. 1901. No. 012047. 8p.
Impagliazzo R. and Wigderson A. p = BPP unless E has subexponential circuits: Derandomizing the XOR Lemma. Proc. 29th STOC. El Paso: ACM, 1997. P.220-229.
Вялый M., Kumaee А., Шенъ А. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо. 1999. 192 с.
О генерической сложности решения уравнений в конечных предикатных алгебраических системах | Прикладная дискретная математика. 2025. № 70. DOI: 10.17223/20710410/70/6
Скачать полнотекстовую версию
Загружен, раз: 28