The main result of this paper is that, for \(n\ge5\), the problem of checking the validity of a given semigroup identity in the twisted Brauer monoid \(\mathcal{B}_n^\tau\) is co-NP-complete. Its elements are pairs \((\pi;s)\) where \(\pi\) is a partition into two-element set of a set of \(2n\) elements and \(s\) is a natural number. The monoid \(\mathcal{B}_n^\tau\) has a natural geometric interpretation and plays a role in representation theory, both well explained in the paper. If one allows \(s\) to assume, more generally, any integer value, one obtains the larger monoid \(\mathcal{B}_n^{\pm\tau}\), which turns out to have a much nicer structure: it is regular, its \(\mathcal{J}\)-classes form an \((n+1)\)-chain and it is stable; up to isomorphism, its maximal subgroups are of a finite symmetric group with an infinite cyclic group. Yet, it satisfies the same identities as \(\mathcal{B}_n^\tau\). The next crucial ingredient in the proof of the main result is the following result which extends the finite case obtained by J. Almeida et al. [J. Math. Sci., New York 158, No. 5, 605–614 (2009; Zbl 1213.20052); translation from Zap. Nauchn. Semin. POMI 358, 5–22 (2008)]: in a stable semigroup \(\mathcal{S}\) with finitely many \(\mathcal{J}\)-classes, the identity checking problem for the direct product of its maximal subgroups reduces to that of \(\mathcal{S}\). The remaining tool used for the proof of the main theorem is a result of G. Horváth et al. [Bull. Lond. Math. Soc. 39, No. 3, 433–438 (2007; Zbl 1167.20019)] that states, for every non-solvable finite group, the identity checking problem is co-NP-complete.
For the entire collection see [Zbl 1531.20003].