Tue, 7 Apr 2026, 1:25 pm MDT
The family of promise constraint satisfaction problems (PCSPs) is a variant of the well studied family of constraint satisfaction problems (CSPs). The computational problem of solving promise systems of equations over algebras is a variant of the problem of systems of equations over algebras. Given two algebras A and B of the same signature such that A maps homomorphically into B, one can ask if a system of equations has a solution in A or if it doesn't even have a solution in B. Given a finite algebra A, it is known that determining whether or not systems of equations over A have a solution is either solvable in polynomial time, or is NP complete (the famous dichotomy theorem for CSPs.) The question of whether or not a dichotomy holds for promise systems of equations over finite algebras is open in general. I will present some dichotomy results for promise systems of equations over various classes of algebras, including Mal'cev algebras.