Prof. Csaba Szabo (Eötvös Loránd University, Budapest) "The complexity of solving equations over finite groups and rings"

Klipi teostus: Rainis Haller 23.04.2014 5164 vaatamist Matemaatika ja matemaatiline statistika



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.