Behrisch, M. (2023). On Weak Bases for Boolean Relational Clones and Reductions for Computational Problems. IfCoLog Journal of Logics and Their Applications, 10(6), 1059–1103. http://hdl.handle.net/20.500.12708/191230
We improve an existence condition for weak bases of relational clones on finite sets. Moreover, we provide a set of singleton weak bases of Boolean relational clones different than those exhibited by Lagerkvist in [24]. We treat groups of ‘similar’ Boolean clones in a uniform manner with the goal of thereby simplifying proofs working by case distinction along the clones in Post’s lattice.
We then present relationships between weak base relations along the covering edges in Post’s lattice, which can (with one exception) be exploited to obtain parsimonious reductions of computational problems related to constraint satisfaction, in which the size of the instance only grows linearly. We also investigate how the number of variables changes between instances in these reductions.
