{"id":"arxiv/2602.00778","url":"https://arxiv.org/abs/2602.00778","tags":["cs.CC","math.RA"],"score":0,"title":"The complexity of finding coset-generating polymorphisms and the promise metaproblem","domain":"cs.CC","source":"arxiv","authors":["Manuel Bodirsky","Armin Weiß"],"reviews":0,"subject":"cs.CC","summary":"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) \\mapsto 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 $Σ_1$ and $Σ_2$ and defined analogously to the promise constraint satisfaction problem. We give sufficient conditions under which the promise…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-31","reactions":{}}