We consider semigroup algorithmic problems in the Special Affine group $\mathsf{SA}(2, \mathbb{Z}) = \mathbb{Z}^2 \rtimes \mathsf{SL}(2, \mathbb{Z})$, which is the group of affine transformations of the lattice $\mathbb{Z}^2$ that preserve orientation. Our paper focuses on two decision problems introduced by Choffrut and Karhum\"{a}ki (2005): the Identity Problem (does a semigroup contain a neutral element?) and the Group Problem (is a semigroup a group?) for finitely generated sub-semigroups of $\mathsf{SA}(2, \mathbb{Z})$. We show that both problems are decidable and NP-complete. Since $\mathsf{SL}(2, \mathbb{Z}) \leq \mathsf{SA}(2, \mathbb{Z}) \leq \mathsf{SL}(3, \mathbb{Z})$, our result extends that of Bell, Hirvensalo and Potapov (SODA 2017) on the NP-completeness of both problems in $\mathsf{SL}(2, \mathbb{Z})$, and contributes a first step towards the open problems in $\mathsf{SL}(3, \mathbb{Z})$.
翻译：我们考虑特殊仿射群$\mathsf{SA}(2, \mathbb{Z}) = \mathbb{Z}^2 \rtimes \mathsf{SL}(2, \mathbb{Z})$中的半群算法问题，该半群是保持方向的格$\mathbb{Z}^2$的仿射变换群。本文重点研究了Choffrut和Karhum\"{a}ki（2005）提出的两个决策问题：恒等问题（半群中是否包含一个中性元素？）和群问题（半群是否为群？）特别是针对$\mathsf{SA}(2, \mathbb{Z})$中的有限生成子半群。我们证明了这两个问题是可判定的并且是NP完全的。由于$\mathsf{SL}(2, \mathbb{Z}) \leq \mathsf{SA}(2, \mathbb{Z}) \leq \mathsf{SL}(3, \mathbb{Z})$，我们的结果扩展了Bell，Hirvensalo和Potapov（SODA 2017）关于$\mathsf{SL}(2, \mathbb{Z})$中这两个问题的NP完全性的结果，并为解决$\mathsf{SL}(3, \mathbb{Z})$中的开放式问题迈出了第一步。
相关内容
微信扫码咨询专知VIP会员