Bounded Bases of Strong Partial Clones

Partial clone theory has successfully been applied to study the complexity of the constraint satisfaction problem parameterized by a set of relations (CSP(Γ)). Lagerkvist & Wahlström (ISMVL 2014) however shows that the partial polymorphisms of Γ (ρPοI(Γ)) cannot be finitely generated for finite, Boolean Γ if CSP(Γ) is NP-hard (assuming P≠NP). In this paper we consider stronger closure operators than functional composition which can generate ρPοI(Γ) from a finite set of partial functions, a bounded base. Determining bounded bases for finite languages provides a complete characterization of their partial polymorphisms and we provide such bases for k-SAT and 1-in-k-SAT.