The wonderland of reflections (Q1709740)

The paper is devoted to the study of the well-known notion of CSPs (constraint satisfaction problems). For a comparison of the complexity of relational structures \(\mathbb A\), \(\mathbb B\), the following reductions expressing that \(\mathrm{CSP}(\mathbb B)\) is at most hard as \(\mathrm{CSP}(\mathbb A)\) are used: {\parindent=7mm \begin{itemize}\item[(a)] \(\mathbb B\) is pp-interpretable in \(\mathbb A\), \item[(b)] \(\mathbb B\) is homomorphically equivalent to \(\mathbb A\), \item[(c)] \(\mathbb A\) is a core and \(\mathbb B\) is obtained from \(\mathbb A\) by adding a singleton unary relation. \end{itemize}} The authors prove a theorem giving a criterion on the structure of the polymorphism clone \(\mathcal A\) of \(\mathbb A\), rather than \(\mathcal B\), which divides NP-hard from polynomial-time solvable CPSs for all finite structures \(\mathbb A\), without necessity to consider their cores. For this purpose, an operator \(\operatorname{E}\) referred to as reflection acting on on function clones is defined: if \(\mathcal A\) is a function clone then \(\operatorname{E}(\mathcal A)\) yields all function clones obtained from \(\mathcal A\) by adding functions to it. Furthermore, a generalization for infinite (countable) categorical structures is dealt with, together with some topological considerations.