The Post correspondence problem in groups.

DOI10.1515/JGTH-2014-0022zbMATH Open1315.20035arXiv1310.5246OpenAlexW2963199596MaRDI QIDQ471848FDOQ471848

Authors: J. Herrera, Sumit K. Garg 

Publication date: 17 November 2014

Published in: Journal of Group Theory (Search for Journal in Brave)

Abstract: We generalize the classical Post correspondence problem ($mathbf{PCP}_n$) and its non-homogeneous variation ($mathbf{GPCP}_n$) to non-commutative groups and study the computational complexity of these new problems. We observe that $mathbf{PCP}_n$ is closely related to the equalizer problem in groups, while $mathbf{GPCP}_n$ is connected to the double twisted conjugacy problem for endomorphisms. Furthermore, it is shown that one of the strongest forms of the word problem in a group $G$ (we call it the {em hereditary word problem}) can be reduced to $mathbf{GPCP}_n$ in $G$ in polynomial time. The main results are that $mathbf{PCP}_n$ is decidable in a finitely generated nilpotent group in polynomial time, while $mathbf{GPCP}_n$ is undecidable in any group containing free non-abelian subgroup (though the argument is very different from the classical case of free semigroups). We show that the double endomorphism twisted conjugacy problem is undecidable in free groups of sufficiently large finite rank. We also consider the bounded $mathbfPCP$ and observe that it is in $mathbfNP$ for any group with $mathbfP$-time decidable word problem, meanwhile it is $mathbfNP$-hard in any group containing free non-abelian subgroup. In particular, the bounded $mathbfPCP$ is $mathbfNP$-complete in non-elementary hyperbolic groups and non-abelian right angle Artin groups.

Full work available at URL: https://arxiv.org/abs/1310.5246

Recommendations

• On some variants of Post's correspondence problem
• Remarks on generalized Post Correspondence Problem
• Post correspondence problem for short words
• The symmetric Post correspondence problem, and errata for the freeness problem for matrix semigroups
• Post correspondence problem with partially commutative alphabets

zbMATH Keywords

computational complexityendomorphismsNP-completenessfree groupsnilpotent groupsArtin groupsword problemPost correspondence problemfree monoidshyperbolic groupstwisted conjugacy problemequalizers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Nilpotent groups (20F18) Free semigroups, generators and relations, word problems (20M05) Word problems (aspects of algebraic structures) (08A50) Word problems, etc. in computability and recursion theory (03D40)

Cited In (13)

• On the dual Post correspondence problem
• Subset sum problem in polycyclic groups
• On subset sum problem in branch groups
• Variations on the post correspondence problem for free groups
• Logspace and compressed-word computations in nilpotent groups
• Parallel complexity for nilpotent groups
• Non-commutative lattice problems
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• Knapsack problems in products of groups
• Post correspondence problem with partially commutative alphabets
• Post's Correspondence Problem for hyperbolic and virtually nilpotent groups
• Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting)
• Post's correspondence problem: from computer science to algebra

This page was built for publication: The Post correspondence problem in groups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q471848)