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.
- 20-06, 20E05, 20F10, 20M05, 68R15