Open AccessA generic algorithm for the identity problem in finite groups and monoids
Author(s) -
Alexander Rybalov
Publication year - 2020
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1546/1/012101
Subject(s) - decidability , algebraic number , time complexity , mathematics , identity (music) , algebra over a field , polynomial , domain (mathematical analysis) , algorithm , computer science , pure mathematics , mathematical analysis , physics , acoustics
Kapovich, Myasnikov, Schupp and Shpilrain in 2003 developed generic approach to algorithmic problems, which considers an algorithmic problem on “most” of the inputs instead of the entire domain and ignores it on the rest of inputs. This approach can be applied to algorithmic problems, which are hard in the classical sense. The problem of checking identities in algebraic structures is the one of the most fundamental problem in algebra. For finite algebraic structures this problem can be decidable in polynomial time, or hard (co-NP-complete). In this paper we present a generic polynomial algorithm for the identity problem in all finite groups and monoids with elements of period greater than 1. The work is supported by Mathematical Center in Akademgorodok, the agreement with Ministry of Science and High Education of the Russian Federation number 075-15-2019-1613.