Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups

DOI10.1090/conm/677/13625zbMath1392.68205arXiv1507.05145OpenAlexW2276040470MaRDI QIDQ2975251

Markus Lohrey, Georg Zetzsche, Daniel König

Publication date: 11 April 2017

Published in: Algebra and Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Nilpotent groups (20F18) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Decidability problem for exponential equations in finitely presented groups ⋮ Post's correspondence problem: from computer science to algebra ⋮ Post's Correspondence Problem for hyperbolic and virtually nilpotent groups ⋮ Knapsack in graph groups ⋮ Closure properties of knapsack semilinear groups ⋮ Knapsack problem for nilpotent groups ⋮ Unnamed Item ⋮ Knapsack in hyperbolic groups ⋮ Low-complexity computations for nilpotent subgroup problems ⋮ On Reachability Problems for Low-Dimensional Matrix Semigroups ⋮ On the Mortality Problem: From Multiplicative Matrix Equations to Linear Recurrence Sequences and Beyond

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Groups, the theory of ends, and context-free languages
• Knapsack problems in products of groups
• The accessibility of finitely presented groups
• On products of subgroups in polycyclic groups
• Finite central height in linear groups
• Rational subsets and submonoids of wreath products.
• Semigroups, Presburger formulas, and languages
• On a problem of Philip Hall
• Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth
• Equations in nilpotent groups
• Evaluating Matrix Circuits
• On the integer solutions of quadratic equations
• Reducibility among Combinatorial Problems
• Rational subsets of unitriangular groups
• The co-word problem for the Higman-Thompson group is context-free
• Computational Complexity
• The Compressed Word Problem for Groups
• GROUPS WITH CONTEXT-FREE CO-WORD PROBLEM
• Knapsack problems in groups
• Shorter Notes: Representations of Polycyclic Groups
• On Context-Free Languages

This page was built for publication: Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups