The Post correspondence problem in groups.

DOI10.1515/JGTH-2014-0022MaRDI QIDQ471848zbMATH OpenOpenAlexFDO

Authors J. Herrera, Sumit K. Garg

Publication date 17 November 2014

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

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

zbMATH Keywords

Artin groupscomputational complexityendomorphismsequalizersfree groupsfree monoidshyperbolic groupsnilpotent groupsNP-completenessPost correspondence problemtwisted conjugacy problemword problem

Mathematics Subject Classification ID

Word problems, etc. in computability and recursion theory (03D40) Word problems (aspects of algebraic structures) (08A50) 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) Analysis of algorithms and problem complexity (68Q25)

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.

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.

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

Cited in

(17)

• Subset sum problem in polycyclic groups
• Computational group theory. Abstracts from the workshop held August 15--21, 2021 (hybrid meeting)
• Non-commutative lattice problems
• Post correspondence problem with partially commutative alphabets
• Parallel complexity for nilpotent groups
• Logspace and compressed-word computations in nilpotent groups
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• On the dual Post correspondence problem
• Post's correspondence problem: from computer science to algebra
• Post's Correspondence Problem for hyperbolic and virtually nilpotent groups
• On subset sum problem in branch groups
• The post correspondence problem and equalisers for certain free group and monoid morphisms
• Contributions to the domino problem: seeding, recurrence and satisfiability
• Undecidability of the stabilizer and zero-in-the-corner problems for matrix groups
• On the intersection of fixed subgroups of F_n F_m
• Variations on the post correspondence problem for free groups
• Knapsack problems in products of groups

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)