The Post correspondence problem in groups.
type: Item
instance of: scholarly article
title: The Post correspondence problem in groups.
zbMATH Open document ID: 1315.20035
author: J. Herrera
author: Sumit K. Garg
published in: Journal of Group Theory
publication date: 2014-11-17T00:00:00Z
full work available at URL: https://arxiv.org/abs/1310.5246
review text: In this paper, the authors continue their research on non-commutative discrete optimization. They generalize the classical Post correspondence problem (PCP) and its non-homogeneous variation (NPCP) to non-commutative groups and study the computational complexity of these new problems. PCP and NPCP are closely related to the equalizer problem and to the double twisted conjugacy problem for endomorphisms, respectively. Recall, that the PCP for any algebraic structure \(\mathbf A\) is to decide, when given two tuples of equal length \(u\) and \(v\) there is a non-trivial term \(t\) such that \(t(u)=t(v)\) in \(\mathbf A\). In 1946, E. Post introduced this problem in the case of free monoids and proved that it is undecidable. Since then PCP took its prominent place in the theory of algorithms and theoretical computer science. The NPCP, designed especially for (semi)groups, is to decide, when given two tuples \(u\) and \(v\) and two elements \(a\) and \(b\) if there is a non-trivial term \(t\) such that \(at(u)=bt(v)\). The authors show that PCP is decidable in a finitely generated nilpotent group in polynomial time, while NPCP is undecidable in any group containing free non-abelian subgroups. Also they prove that the double endomorphism twisted conjugacy problem is undecidable in free groups of sufficiently large finite rank. The bounded PCP is also considered in the paper. It is observed that it is in NP for any group with P-time decidable word problem, meanwhile it is NP-hard in any group containing free non-abelian subgroups.
Mathematics Subject Classification ID: 20F10
Mathematics Subject Classification ID: 03D40
Mathematics Subject Classification ID: 20F18
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 08A50
zbMATH DE Number: 6370193
zbMATH Keywords: free groups
zbMATH Keywords: nilpotent groups
zbMATH Keywords: free monoids
zbMATH Keywords: Post correspondence problem
zbMATH Keywords: endomorphisms
zbMATH Keywords: twisted conjugacy problem
zbMATH Keywords: equalizers
zbMATH Keywords: computational complexity
zbMATH Keywords: word problem
zbMATH Keywords: NP-completeness
zbMATH Keywords: hyperbolic groups
zbMATH Keywords: Artin groups
reviewed by: Vitaliĭ Roman'kov
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2963199596
arXiv ID: 1310.5246
DOI: 10.1515/JGTH-2014-0022
description: scientific article