| Генерическая сложность задачи поиска изоморфизма конечных группоидов | |
| Горкун И. Ф.1 | |
| 1.1Омский государственный университет им. Ф. М. Достоевского, Омск | |
| Дата поступления 2024.09.10 | Аннотация. Генерический подход к алгоритмическим проблемам был предложен Мясниковым, Каповичем, Шуппом и Шпильрайном в 2003 году. Этот подход изучает поведение алгоритма не на всем множестве входов, а на некотором подмножестве (почти всех) входов. В этой статье мы рассматриваем генерическую сложность задачи поиска изоморфизма конечных группоидов и доказываем, что ее естественная подзадача является генерически сложной при условии, что задача поиска изоморфизма конечных группоидов является трудной в худшем случае. |
| Ключевые слова генерическая сложность, группоид, изоморфизм конечных группоидо | |
Библиография \bibitem{KMSS} \textit{Kapovich~I., Myasnikov A., Schupp P., Shpilrain V.} Generic-case complexity, decision problems in group theory and random walks~// J. Algebra. -- 2003. --~Vol.~264, iss.~2. --~P.~665--694. \bibitem{Ryb} \textit{Rybalov A. N.} On the generic complexity of the searching graph isomorphism problem~// Groups Complexity Cryptology. --~2015. --~Vol.~7, iss.~2. --~P.~191--194. | |
Сведения о финансировании и благодарности | |
| {Generic complexity of the problem of searching isomorphism of~finite groupoids | |
| Gorkun I. F.1 | |
| 1.1Dostoevsky Omsk State University | |
| Received 2024.09.10 | Abstract. The generic approach to algorithmic problems was proposed by Myasnikov, Kapovich, Schupp, and Spielrein in 2003. This approach studies the behavior of the algorithm not on the entire set of inputs, but on a certain subset (almost all) of the inputs. In this paper, we consider the general complexity of the finite groupoid isomorphism problem and prove that its natural subproblem is generically hard provided that the finite groupoid isomorphism problem is worst-case hard. |
| Keywords generic complexity, groupoid, isomorphism of finite groupoids | |
References \bibitem{KMSS} \textit{Kapovich~I., Myasnikov A., Schupp P., Shpilrain V.} Generic-case complexity, decision problems in group theory and random walks~// J. Algebra. -- 2003. --~Vol.~264, iss.~2. --~P.~665--694. \bibitem{Ryb} \textit{Rybalov A. N.} On the generic complexity of the searching graph isomorphism problem~// Groups Complexity Cryptology. --~2015. --~Vol.~7, iss.~2. --~P.~191--194. | |
Acknowledgements | |
| Сведения об авторах Горкун И. Ф. 1.1 |
| About the authors Gorkun I. F. 1.1 |
