Showing cs.CCShow all
2 papers · 1 filter
cs.CC2026
The complexity of finding coset-generating polymorphisms and the promise metaproblem
Manuel Bodirsky, Armin WeiÃ
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 whe…
cs.CC2025
Membership and Conjugacy in Inverse Semigroups
Lukas Fleischer, Florian Stober, Alexander Thumm +1
The membership problem for an algebraic structure asks whether a given element is contained in some substructure, which is usually given by generators. In this work we study the me…