2026-09-08T01:22:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26557 2026-09-05T19:47:35Z ddc:004 open_access

The Complexity of Finding Coset-Generating Polymorphisms and the Promise Metaproblem Bodirsky, Manuel Weiß, Armin constraint satisfaction problem coset-generating polymorphisms metaproblem heap abelian heap uniform polynomial-time algorithm NP-hardness We show that the metaproblem for coset-generating polymorphisms is NP-complete, answering a question of Chen and Larose: given a finite structure, the computational question is whether this structure has a polymorphism of the form (x,y,z) ↦ x y^{-1} z with respect to some group; such operations are also called coset-generating, or heaps. Furthermore, we introduce a promise version of the metaproblem, parametrised by two polymorphism conditions Σ₁ and Σ₂ and defined analogously to the promise constraint satisfaction problem. We give sufficient conditions under which the promise metaproblem for (Σ₁,Σ₂) is in 𝖯 and under which it is NP-hard. In particular, the promise metaproblem is in 𝖯 if Σ₁ states the existence of a Maltsev polymorphism and Σ₂ states the existence of an abelian heap polymorphism - despite the fact that neither the metaproblem for Σ₁ nor the metaproblem for Σ₂ is known to be in 𝖯. We also show that the creation-metaproblem for Maltsev polymorphisms, under the promise that a heap polymorphism exists, is in 𝖯 if and only if there is a uniform polynomial-time algorithm for CSPs with a heap polymorphism. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky and Armin Weiß 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.169 urn:nbn:de:0030-drops-265574 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.169 eng https://creativecommons.org/licenses/by/4.0/legalcode