A polynomial characterization of congruence classes (Q1272103)

Let \(C\) be a nonvoid subset of an algebra \(A\) from a regular and permutable variety \(\mathcal V.\) The authors give an explicit list \(L\) of polynomials such that \(C\) is a congruence block in \(A\) iff \(C\) is closed under all polynomials from \(L.\) If \(\mathcal V\) has a finite similarity type, \(L\) is finite. If also \(A\in \mathcal V\) is finite, polynomials of \(L\) can be considered to be unary. Finally, it is shown that the problem of deciding whether \(C\) is a congruence block of a finite algebra \(A\in \mathcal V\) is in NP but for arbitrary \(A\in \mathcal V\) it is in P.