Weak bases for relational clones and their uses

A weak base of a relational clone 𝑄 on a finite set is a finite generating system 𝑊 ⊆ 𝑄 of 𝑄 = [𝑊]∃∧= that generates the smallest weak system 𝑆_𝑄 = [𝑊]∧= among all weak systems 𝑆 with equality having the property Pol 𝑆 = Pol 𝑄, that is, among those relational systems 𝑆 = [𝑆]∧= sharing the same polymorphisms with 𝑄. Many computational problems in theoretical computer science are parametrised by finite sets of relations, for example, constraint satisfaction problems, or they can be rephrased in that form. The relative difficulty of such computational problems is compared using an appropriate notion of reduction for the type of problem (e.g., decision, counting, optimisation, approximation problem etc.). If 𝑅, 𝑅' are finite parameter sets of relations, then expressibility relationships of the form 𝑅 ⊆ [𝑅'] typically lead to reductions 𝖯(𝑅) ≤ 𝖯(𝑅') among the parametrised problems. Here [ ] denotes a closure operator on finitary relations that is appropriate for the type of problem 𝖯 and the sort of reduction ≤ under consideration. The most basic closure that works for many problems and reductions is expressibility by conjunctive formulæ [ ]∧=; a familiar expressibility notion that works for constraint satisfaction decision problems (but not in every other case) is primitive positive closure [ ]∃∧=. Weak bases can help to reduce the effort of obtaining sufficiently many reductions in complexity classifications by lowering the strength of the closure operator [ ] for which one needs to show that 𝑅 ⊆ [𝑅'] implies 𝖯(𝑅) ≤ 𝖯(𝑅'): namely, the operator [ ] = [ ]∧= suffices for arbitrary weak bases, and the even weaker closure [ ] = [ ]∧ suffices for weak bases consisting of irredundant proper relations. In the context of complexity classifications, weak bases with irredundant proper relations can thus be used to identify weakest hard problems. In the talk we shall review some details of how this works, look at concrete families of weak bases, consider problems where this approach has been successfully applied in the past, and discuss some recent results about weak bases, as well as some prospects for future investigation.