一句话：证明 Z^2 特殊仿射群中有限生成子半群的 Identity Problem 与 Group Problem 均可判定且 NP-完全。
本文研究特殊仿射群 SA(2,Z)=Z^2 ⋊ SL(2,Z) 中有限生成子半群的算法问题，即 Choffrut 与 Karhumäki 提出的 Identity Problem（半群是否包含单位元）和 Group Problem（半群是否为群）。作者针对这两个判定问题给出可判定性证明，并进一步确定其复杂度均为 NP-完全。由于 SL(2,Z) ≤ SA(2,Z) ≤ SL(3,Z)，该结果推广了 Bell、Hirvensalo 与 Potapov 关于 SL(2,Z) 中两问题 NP-完全性的结论，同时为 SL(3,Z) 中的公开问题提供了进展。
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 (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})$.