Algebra Seminar talk
2018-03-23 (10:15)
Michael Kompatscher (Univerzita Karlova, Prag)
The equation solvability problem
Abstract:
One of the oldest problems in algebra is solving equations, i.e. answering whether an equation over a given algebraic structure has a solution or not. In the last decades this problem received increasing interest from a complexity point of view. In particular the question is, over which finite algebras the equation solvability problem in P and over which it is NP-complete. Finding such characterization seems to be very difficult in general. But for certain classes of algebras (groups, rings, lattices) complete complexity classifications are known. In my talk I would like to show how the known tractability results can be generalized to supernilpotent algebras from congruence modular varieties and discuss what steps are still missing in proving a complexity dichotomy in the congruence modular case.