2 results
Filters
Settings
Now showing1 - 2 of 2
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Finite algebras with hom-sets of polynomal sizeWe provide an internal characterization of those finite algebras (i.e., algebraic structures) A such that the number of homomorphisms from any finite algebra X to A is bounded from above by a polynomial in the size of X. Namely, an algebra A has this property if, and only if, no subalgebra of A has a nontrivial strongly abelian congruence. We also show that the property can be decided in polynomial time for algebras in finite signatures. Moreover, if A is such an algebra, the set of all homomorphisms from X to A can be computed in polynomial time given X as input. As an application of our results to the field of computational complexity, we characterize inherently tractable constraint satisfaction problems over fixed finite structures, i.e., those that are tractable and remain tractable after expanding the fixed structure by arbitrary relations or functions.Publicationtype: Journal Article25 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , ω-categorical structures avoiding height 1 identitiesThe algebraic dichotomy conjecture for Constraint Satisfaction Problems (CSPs) of reducts of (infinite) finitely bounded homogeneous structures states that such CSPs are polynomial-time tractable if the model-complete core of the template has a pseudo-Siggers polymorphism, and is NP-complete otherwise. One of the important questions related to the dichotomy conjecture is whether, similarly to the case of finite structures, the condition of having a pseudo-Siggers polymorphism can be replaced by the condition of having polymorphisms satisfying a fixed set of identities of height 1, i.e., identities which do not contain any nesting of functional symbols. We provide a negative answer to this question by constructing for each nontrivial set of height 1 identities a structure within the range of the conjecture whose polymorphisms do not satisfy these identities, but whose CSP is tractable nevertheless. An equivalent formulation of the dichotomy conjecture characterizes tractability of the CSP via the local satisfaction of nontrivial height 1 identities by polymorphisms of the structure. We show that local satisfaction and global satisfaction of nontrivial height 1 identities differ for ω-categorical structures with less than doubly exponential orbit growth, thereby resolving one of the main open problems in the algebraic theory of such structures.Publicationtype: Journal Article29