In the past few decades computational complexity questions over finite algebraic structures are gaining more and more interest. In my talk I review the existing results on the most natural questions: the equation solvability and the identity checking problems. Given a finite algebra A and two several variable terms (polynomials) p(x1,…,xn), q(x1,…,xn ) over A. The equation solvability question asks if there are any elements a1,a2,…,an such that p(a1,…,an)=q(a1,…,an). The identity checking question asks if the same holds for every substitution of the variables. I will discuss these complexity questions over classical algebraic structures as groups and rings and I will pose several open problems.
Eesti matemaatika ja statistika doktorikooli seminar 23. aprillil 2014. a kell 14:15-16:00 Tartus J. Liivi 2-224.
Filmis: Valdis Laan.