Showing cs.CCShow all
3 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.CC2026
Graph Homomorphisms and Universal Algebra
Manuel Bodirsky
Constraint satisfaction problems are computational problems that naturally appear in many areas of theoretical computer science. One of the central themes is their computational co…
cs.CC2025
Polynomial-time Tractable Problems over the -adic Numbers
Arno Fehm, Manuel Bodirsky
We study the computational complexity of fundamental problems over the -adic numbers and the -adic integers . Guépin, Haase, and Worrell prove…