Post's Correspondence Problem for hyperbolic and virtually nilpotent groups

Research output: Contribution to journalArticlepeer-review


Post’s Correspondence Problem (the PCP) is a classical decision problem in theoretical computer science that asks whether for pairs of free monoid morphisms g,ℎ∶ Σ → Δ there exists any non-trivial 𝑥∈Σ such that g(𝑥) = ℎ(𝑥). PCP for a group Γ takes pairs of group homomorphisms g, ℎ ∶ 𝐹(Σ) → Γ instead, and similarly asks whether there exists an 𝑥 such that g(𝑥) = ℎ(𝑥) holds for non-elementary reasons. The restrictions imposed on 𝑥 in order to get non-elementary solutions lead to several interpretations of the problem; we mainly consider the natural restriction asking that 𝑥 ∉ ker(g) ∩ ker(ℎ) and prove that the resulting interpretation of the PCP is undecidable for arbitrary hyperbolic Γ, but decidable when Γ is virtually nilpotent, en route also studying this problem for finite extensions. We also consider a different interpretation of the PCP due to Myasnikov, Nikolaev and Ushakov, proving decidability for torsion-free nilpotent groups.
Original languageEnglish
JournalBulletin of the London Mathematical Society
Early online date9 Sept 2023
Publication statusE-pub ahead of print - 9 Sept 2023


  • math.GR
  • cs.CC
  • cs.LO
  • 20-06, 20E05, 20F10, 20M05, 68R15

Cite this