The Post correspondence problem in groups. (Q471848)

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.