Knapsack and the power word problem in solvable Baumslag–Solitar groups

DOI10.1142/s0218196723500285zbMath1516.20066OpenAlexW3040259253MaRDI QIDQ6159137

Georg Zetzsche, Markus Lohrey, Moses Ganardi

Publication date: 1 June 2023

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218196723500285

zbMATH Keywords

Baumslag-Solitar groupscomputational group theorymatrix problems

Mathematics Subject Classification ID

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) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (2)

The Diophantine problem for systems of algebraic equations with exponents ⋮ Quadratic equations in metabelian Baumslag–Solitar groups

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Knapsack problem for nilpotent groups
• Wreath products and finitely presented groups
• Knapsack problems in products of groups
• Logic and \(p\)-recognizable sets of integers
• Generators of split extensions of abelian groups by cyclic groups
• Knapsack in graph groups
• Evaluation of circuits over nilpotent and polycyclic groups
• Uniform constant-depth threshold circuits for division and iterated multiplication.
• The power word problem in graph products
• Closure properties of knapsack semilinear groups
• Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• LIMITS OF METABELIAN GROUPS
• Weak Second‐Order Arithmetic and Finite Automata
• Knapsack Problems for Wreath Products
• Very Fast Parallel Polynomial Arithmetic
• Definability in the Existential Theory of Concatenation and Undecidable Extensions of this Theory
• The Complexity of theA B CProblem
• The word and geodesic problems in free solvable groups
• Random Walks on Infinite Graphs and Groups
• Elementary Methods in Number Theory
• Computational Complexity
• The Compressed Word Problem for Groups
• Knapsack problems in groups
• On Artin's conjecture.
• Knapsack in hyperbolic groups

This page was built for publication: Knapsack and the power word problem in solvable Baumslag–Solitar groups