Non-commutative lattice problems

2015/08/10 by Myasnikov, Alexei, Nikolaev, Andrey, Ushakov, Alexander
#03D15 #20F10 #20F65 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Group Theory (math.GR)

paper · doi:10.48550/arxiv.1508.02388

Abstract

We consider several subgroup-related algorithmic questions in groups, modeled after the classic computational lattice problems, and study their computational complexity. We find polynomial time solutions to problems like finding a subgroup element closest to a given group element, or finding a shortest non-trivial element of a subgroup in the case of nilpotent groups, and a large class of surface groups and Coxeter groups. We also provide polynomial time algorithm to compute geodesics in given generators of a subgroup of a free group.

Related

• Low-complexity computations for nilpotent subgroup problems
• Computational Complexity of Finding Subgroups of a Given Order
• The Post correspondence problem in groups
• Coxeter Groups, 2-Completion, Perimeter Reduction and Subgroup Separability
• Complexity of some algorithmic problems in groups: a survey