Charles University Chapter of SIAM

Naše akce - Seminář SIAM SC - Další akce

Michael Kompatscher – The complexity of solving equations

Kdy: 04/03/2020 14:00 - 04/03/2020 15:30
Kde: Seminární místnost MUUK (3. patro)

One of the oldest problems in algebra is to decide whether an equation over a given algebraic structure has a solution or not. In the last decades this problem received increasing interest from computational complexity point of view. 
For finite algebras the naive algorithm of 'guessing' solutions always works (and thus the problem is in NP). However for many algebras algorithms with better, i.e. polynomial, runtime are known (e.g. Gaussian elimination). In particular groups, rings and lattices that allow polynomial-time algorithms are (almost) completely classified. In my talk I would like to give an introduction to these results and discuss some of the difficulties in generalizing them to all finite algebras.

poster