Title :
Bounded Bases of Strong Partial Clones
Author :
Lagerkvist, Victor ; Wahlstrom, Magnus ; Zanuttini, Bruno
Author_Institution :
Dept. of Comput. & Inf. Sci., Linkopings Univ., Linköping, Sweden
Abstract :
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.
Keywords :
computational complexity; functions; set theory; Γ (ρPοI(Γ)); bounded base; closure operators; partial functions; partial polymorphisms; strong partial clone; Assistive technology; Cloning; Context; Electronic mail; Lattices; NP-hard problem; Clone theory; constraint satisfaction; partial clone theory;
Conference_Titel :
Multiple-Valued Logic (ISMVL), 2015 IEEE International Symposium on
Conference_Location :
Waterloo, ON
DOI :
10.1109/ISMVL.2015.33
