Fine-grained complexity of constraint satisfaction problems through partial polymorphisms: A survey
M Couceiro, L Haddad… - 2019 IEEE 49th …, 2019 - ieeexplore.ieee.org
Constraint satisfaction problems (CSPs) are combinatorial problems with strong ties to
universal algebra and clone theory. The recently proved CSP dichotomy theorem states that …
universal algebra and clone theory. The recently proved CSP dichotomy theorem states that …
A survey on the fine-grained complexity of constraint satisfaction problems based on partial polymorphisms
M Couceiro, L Haddad, V Lagerkvist - … of Multiple-Valued Logic and Soft …, 2022 - hal.science
Constraint satisfaction problems (CSPs) are combinatorial problems with strong ties to
universal algebra and clone theory. The recently proved CSP dichotomy theorem states that …
universal algebra and clone theory. The recently proved CSP dichotomy theorem states that …
The inclusion structure of Boolean weak bases
V Lagerkvist, B Roy - 2019 IEEE 49th International Symposium …, 2019 - ieeexplore.ieee.org
Strong partial clones are composition closed sets of partial operations containing all partial
projections, characterizable as partial polymorphisms of sets of relations Γ (pPol (Γ)). If C is a …
projections, characterizable as partial polymorphisms of sets of relations Γ (pPol (Γ)). If C is a …
[PDF][PDF] C-Maximal Strong Partial Clones and the Inclusion Structure of Boolean Weak Bases.
V Lagerkvist, B Roy - J. Multiple Valued Log. Soft Comput., 2022 - victorlagerkvist.github.io
Strong partial clones are composition closed sets of partial operations containing all partial
projections, characterizable as partial polymorphisms of sets of relations Γ (pPol (Γ)). If C is a …
projections, characterizable as partial polymorphisms of sets of relations Γ (pPol (Γ)). If C is a …
On the strength of uniqueness quantification in primitive positive formulas
V Lagerkvist, G Nordh - arXiv preprint arXiv:1906.07031, 2019 - arxiv.org
Uniqueness quantification ($\exists! $) is a quantifier in first-order logic where one requires
that exactly one element exists satisfying a given property. In this paper we investigate the …
that exactly one element exists satisfying a given property. In this paper we investigate the …
Algebraic Global Gadgetry for Surjective Constraint Satisfaction
H Chen - computational complexity, 2024 - Springer
The constraint satisfaction problem (CSP) on a finite relational structure B is to decide, given
a set of constraints on variables where the relations come from B, whether or not there is an …
a set of constraints on variables where the relations come from B, whether or not there is an …
Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey (Dedicated to the memory of Professor Ivo Rosenberg)
M Couceiro, L Haddad, V Lagerkvist - ISMVL2019-IEEE 49th …, 2019 - inria.hal.science
Constraint satisfaction problems (CSPs) are combi-natorial problems with strong ties to
universal algebra and clone theory. The recently proved CSP dichotomy theorem states that …
universal algebra and clone theory. The recently proved CSP dichotomy theorem states that …