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

О генерической сложности решения уравнений над бициклическим моноидом | Прикладная дискретная математика. 2025. № 67. DOI: 10.17223/20710410/67/6

Изучается вычислительная сложность проблемы проверки разрешимости систем уравнений над бициклическим моноидом. Этот моноид, помимо теоретического значения в топологии и теории полугрупп, имеет приложения в информатике и языках программирования, например как модель для языка Дика сбалансированных скобочных выражений. Доказывается NP-полнота проблемы проверки разрешимости систем уравнений над бициклическим моноидом. Также доказывается, что при P = NP и P = BPP для этой проблемы не существует сильно генерического полиномиального алгоритма. Это означает, что для любого генерического полиномиального алгоритма имеется эффективный метод случайной генерации входов, на которых этот алгоритм не может решить рассматриваемую проблему. Полученный результат указывает на возможное применение данной проблемы в криптографии, где нужно, чтобы проблема взлома криптосистемы была трудной для почти всех входов.
  • Title О генерической сложности решения уравнений над бициклическим моноидом
  • Headline О генерической сложности решения уравнений над бициклическим моноидом
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 67
  • Date:
  • DOI 10.17223/20710410/67/6
Ключевые слова
генерическая сложность, NP-полнота, бициклическим моноид
Авторы
Ссылки
Рыбалов А. Н. О сложности решения уравнений над графами // Сиб. электрон. матем. изв. 2024. T.21. №1. С. 62-69.
Шевляков А. Н. Сплетения полугрупп и проблема Б. И. Плоткина // Алгебра и логика. 2023. Т. 62. №5. С. 665-691.
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. Equationally Noetherian varieties of semigroups and B. Plotkin's problem // Сиб. электрон. матем. изв. 2023. Т. 20. № 2. С. 724-734.
Nikitin A. Yu. and Shevlyakov A. N. On radicals over strict partial order sets // J. Physics: Conf. Ser. 2021. V. 1791. No. 012080. P. 1-6.
Kapovich I., Miasnikov A., Schupp P., 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. Physics: Conf. Ser. 2021. V. 1901. No. 012047. P. 1-8.
Hopcroft J. E. and Ullman J. D. Formal Languages and Their Relation to Automata. Addison-Wesley, 1969. 288 p.
Diekert V. and Lohrey M. Word equations over graph products // Intern. J. Algebra Computation. 2008. V. 18. No. 3. P. 493-533.
Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. М.: МЦНМО, ЧеРо, 1999. 192 с.
Схрейвер А. Теория линейного и целочисленного программирования. М.: Мир, 1991. 360 с.
О генерической сложности решения уравнений над бициклическим моноидом | Прикладная дискретная математика. 2025. № 67. DOI: 10.17223/20710410/67/6
О генерической сложности решения уравнений над бициклическим моноидом | Прикладная дискретная математика. 2025. № 67. DOI: 10.17223/20710410/67/6