The Post correspondence problem in groups.

DOI10.1515/jgth-2014-0022zbMath1315.20035arXiv1310.5246OpenAlexW2963199596MaRDI QIDQ471848

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

computational complexityendomorphismsArtin groupsword problemnilpotent groupshyperbolic groupsNP-completenessfree groupsfree monoidstwisted conjugacy problemPost correspondence problemequalizers

Mathematics Subject Classification ID

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

Related Items

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