Abstract
In this note, we show that the knapsack problem is decidable in Baumslag-Solitar groups $BS(1,q)$ for $q \ge 2$.
Introduction
Baumslag-Solitar groups, denoted as $BS(p, q)$, are a fundamental class of groups in geometric group theory, defined by the presentation $\langle a, t \mid ta^p t^{-1} = a^q \rangle$. These groups serve as a vital testing ground for algorithmic decision problems due to their varied structural properties. This research focuses on the solvable (metabelian) case where $p=1$, specifically $BS(1, q)$ for $q \ge 2$. The study maps the computational landscape of three nested decision problems: the power word problem, the knapsack problem, and systems of exponent equations.
The Power Word Problem
The word problem is the most basic decision problem in group theory: given a word in the generators, does it represent the identity? The power word problem is a succinct version where the input consists of group elements $g_i$ and exponents $n_i$ encoded in binary. The goal is to determine if $g_1^{n_1} g_2^{n_2} \dots g_k^{n_k} = 1$.
The authors demonstrate that for $BS(1, q)$, this problem is in $TC^0$, the complexity class of problems solvable by constant-depth circuits with threshold gates. This result is achieved by representing group elements as $2 \times 2$ matrices and applying a "Gap Theorem" for sparse polynomials. If a product of powers does not equal the identity, its matrix representation must be sufficiently far from zero, allowing for efficient verification in a highly parallelizable manner.
The Knapsack Problem
The knapsack problem in a group $G$ asks whether, given elements $g_1, \dots, g_d$ and a target element $h$, there exist non-negative integers $x_1, \dots, x_d$ such that: $$g_1^{x_1} g_2^{x_2} \dots g_d^{x_d} = h$$
In $BS(1, q)$, the authors prove this problem is NP-complete. The complexity is particularly interesting because the smallest solutions $x_i$ can be doubly exponential relative to the input size. This prevents a standard "guess-and-verify" approach, as the witness itself is too large to be read in polynomial time. Instead, the proof relies on a reduction to the existential fragment of Büchi arithmetic—a logic that extends Presburger arithmetic with a function $V_q(x)$ that returns the largest power of $q$ dividing $x$. By leveraging recent results showing this fragment is in NP, the authors establish the decidability and complexity of the knapsack problem for these groups.
Systems of Exponent Equations
The research identifies a sharp boundary for decidability. When the knapsack problem is generalized to systems of exponent equations—where variables can appear multiple times across different equations—the problem becomes undecidable.
This undecidability is proven by reducing from the existential theory of $(\mathbb{N}, +, (x, y) \mapsto x \cdot 2^y)$. This logic is known to be undecidable, and the authors show that the structure of $BS(1, q)$ is rich enough to encode these operations. This highlights a transition: while a single knapsack equation is manageable, the interaction between multiple equations allows for the simulation of complex logical structures equivalent to the Halting Problem.
Methodology
The proofs leverage several sophisticated techniques from theoretical computer science:
- Matrix Representations: Mapping $BS(1, q)$ to $2 \times 2$ matrices over algebraic numbers to transform group operations into polynomial arithmetic.
- Sparse Polynomial Root Testing: Checking if polynomials with many terms but few non-zero coefficients evaluate to zero at specific points.
- Logical Reductions: Using the properties of Büchi arithmetic for NP-membership and known undecidable fragments of arithmetic for the systems of equations.
Conclusion and Future Work
This work settles the complexity of the knapsack problem for metabelian Baumslag-Solitar groups, placing it firmly in NP-complete. However, several questions remain:
- General Baumslag-Solitar Groups: The complexity for $BS(p, q)$ where $p, q \ge 2$ remains largely open. These groups are not solvable and exhibit much more "wild" behavior.
- Compressed Word Problem: The exact complexity of the compressed word problem (where words are given as straight-line programs) for $BS(1, q)$ is currently narrowed down only to $coRP$.
- Matrix Groups: The authors suggest further investigation into whether the knapsack problem is decidable for every matrix group generated by the specific matrices used in their proofs, particularly when the base is not an integer.
Summary updated