The word problem of the Brin-Thompson group is coNP-complete
arXiv:1902.03852
Abstract
We prove that the word problem of the Brin-Thompson group nV over a finite generating set is coNP-complete for every n \ge 2. It is known that the groups nV are an infinite family of infinite, finitely presented, simple groups. We also prove that the word problem of the Thompson group V over a certain infinite set of generators, related to boolean circuits, is coNP-complete.
arXiv comment38 pages
References in corpus (5)
- Higher Dimensional Thompson Groups
- On the Baker's map and the Simplicity of the Higher Dimensional Thompson Groups nV
- Presentations of higher dimensional Thompson groups
- Circuits, coNP-completeness, and the groups of Richard Thompson
- Rigidity properties of full groups of pseudogroups over the Cantor set