Complexity of properties of computable magmas
Jennifer Chubb, Valentina Harizanov, Dario Verta · Contemporary mathematics - American Mathematical Society · 2025
A magma is an algebraic structure with a single binary operation. Magmas include semigroups, groups, quandles, and other structures of importance in algebra, topology, and physics. Quandles are certain right self-distributive magmas, which are not necessarily associative. A magma is computable if its domain is a computable set and its operation is computable. We investigate the algorithmic complexity of natural properties on computable magmas, which are Π 1 0 \Pi _{1}^{0} or Π 2 0 \Pi _{2}^{0} in Kleene-Mostowski arithmetical hierarchy. A property is Π 1 0 \Pi _{1}^{0} if it can be stated using a universal quantifier followed by a decidable predicate. A property is Σ 2 0 \Sigma _{2}^{0} if it can be stated using an existential quantifier followed by a Π 1 0 \Pi _{1}^{0} property. Inspired by the study of Markov properties of groups, we formulate general conditions for determining Π 1 0 \Pi _{1}^{0} -hardness and Π 2 0 \Pi _{2}^{0} -hardness of certain problems on computable magmas. We obtain hardness by using computable reductions of known hard problems in computability theory. Hardness together with definability of properties allows us to calibrate exact complexity of various properties.