Tue, 21 Mar 2023, 1:25 pm MDT
The talk reports how the project of characterizing finite algebras with tractable equation solving problem led us to the concepts of circuits and non-uniform automata over arbitrary algebras.
As a byproduct we get (under some complexity hypothesis, like Exponential Time Hypothesis and Constant Degree Hypothesis) a full characterization of finite algebras from congruence modular varieties with tractable checking if two circuits compute the same function. A similar (but not the same one) characterization is also provided for finite groups with respect to checking if two polynomials define the same function.