The complexity of finding coset-generating polymorphisms and the promise metaproblem
Publikation: Vorabdruck/Dokumentation/Bericht › Vorabdruck (Preprint)
Beitragende
Abstract
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 metaproblem for $(Σ_1,Σ_2)$ is in P and under which it is NP-hard. In particular, the promise metaproblem is in P if $Σ_1$ states the existence of a Maltsev polymorphism and $Σ_2$ states the existence of an abelian heap polymorphism -- despite the fact that neither the metaproblem for $Σ_1$ nor the metaproblem for $Σ_2$ is known to be in P. We also show that the creation-metaproblem for Maltsev polymorphisms, under the promise that a heap polymorphism exists, is in P if and only if there is a uniform polynomial-time algorithm for CSPs with a heap polymorphism.
Details
| Originalsprache | Englisch |
|---|---|
| Seitenumfang | 18 |
| Publikationsstatus | Veröffentlicht - 31 Jan. 2026 |
No renderer: customAssociatesEventsRenderPortal,dk.atira.pure.api.shared.model.researchoutput.WorkingPaper
Externe IDs
| ORCID | /0000-0001-8228-3611/work/208071928 |
|---|
Schlagworte
Schlagwörter
- cs.CC, math.RA