Abstract
The Number Balancing Problem (NBP) asks for two disjoint subsets of a given set of real numbers $a_1, \ldots, a_n \in [0, 1]$ such that the difference between their sums is minimized. While the pigeonhole principle guarantees the existence of a solution with a difference as small as $O(\frac{\sqrt{n}}{2^n})$, finding the minimum is NP-hard. For decades, the best known polynomial-time approach has been the 1982 Karmarkar-Karp differencing algorithm, which achieves a difference of $n^{-\Theta(\log n)}$. This paper establishes a deep, bidirectional relationship between NBP and Minkowski's Theorem. We demonstrate that an approximate oracle for Minkowski's Theorem provides an approximate NBP oracle and, more significantly, that a sufficiently accurate NBP oracle can solve the Shortest Vector Problem (SVP) and Minkowski's problem within polynomial factors. Specifically, any polynomial-time algorithm guaranteeing a solution of at most $2^{\sqrt{n}} / 2^{n}$ would imply a polynomial approximation for these fundamental lattice problems.
Introduction
The Number Balancing Problem (NBP) is a classic variation of the subset-sum and partition problems. Formally, given a vector $a = (a_1, \dots, a_n) \in [0, 1]^n$, we seek a non-zero vector $x \in \{-1, 0, 1\}^n$ that minimizes the absolute value of the inner product $|\langle a, x \rangle|$.
This problem sits at a fascinating intersection of combinatorics and computational complexity. On one hand, non-constructive proofs (the pigeonhole principle) tell us that extremely good balances exist. On the other hand, the algorithmic gap is massive: the difference between the $2^{-n}$ scale guaranteed by theory and the $n^{-\log n}$ scale achievable by the Karmarkar-Karp algorithm has remained unbridged for over thirty years. This research clarifies why this gap exists by linking NBP to the geometry of numbers.
The Geometric Connection: Minkowski’s Theorem
The authors reframe NBP through the lens of Minkowski’s Theorem, a cornerstone of lattice theory. Minkowski’s Theorem states that any centrally symmetric convex body in $\mathbb{R}^n$ with a sufficiently large volume must contain a non-zero integer point.
In the context of NBP, the problem can be viewed as searching for an integer point (the sign vector $x$) within a specific geometric region—a "slab" defined by the hyperplane $\langle a, x \rangle = 0$. The paper establishes two primary reductions that prove NBP is essentially as difficult as finding short vectors in a lattice.
1. From Minkowski to NBP
The first reduction shows that an oracle capable of finding integer points in symmetric convex bodies (an approximate Minkowski oracle) can be used to solve NBP. By constructing a convex body that represents the constraints of the number balancing problem, the authors prove that the existence of a balancing vector is a direct consequence of Minkowski’s volume arguments. This provides a geometric upper bound on the achievable balance.
2. From NBP to Minkowski (The Hardness of NBP)
The more striking contribution is the reverse reduction. The authors prove that if one could find a "high-quality" solution to NBP in polynomial time, one could also solve the Shortest Vector Problem (SVP) in the $L_\infty$ norm.
To achieve this, the authors employ several sophisticated mathematical tools:
- John’s Theorem: Used to approximate arbitrary convex bodies with ellipsoids.
- LLL Lattice Reduction: Used to "regularize" these ellipsoids into a form where NBP techniques can be applied.
- Recursive Self-Reduction: The authors developed a technique to boost a moderately successful NBP solver. By repeatedly applying an NBP oracle to smaller sub-problems, they can refine a coarse balance into an extremely precise one, eventually revealing the shortest vector in a general lattice.
Key Results and Complexity Implications
The paper provides explicit bounds on the hardness of NBP relative to lattice problems:
- Theorem 1: A $\rho$-approximation for Minkowski’s problem yields a $\delta$-approximation for NBP, where the error $\delta$ is exponentially small: $2^{-n^{\Theta(1/\rho)}}$.
- Theorem 3: Any polynomial-time algorithm guaranteeing an NBP solution with an error at most $2^{\sqrt{n}}/2^n$ would provide an $O(n^5)$-approximation for Minkowski’s problem.
These results suggest that the difficulty of improving the Karmarkar-Karp algorithm is not merely a technical hurdle but is tied to the fundamental hardness of lattice-based problems. Since many modern post-quantum cryptographic protocols rely on the hardness of SVP, this equivalence suggests that NBP is a "hard" problem in a very formal, cryptographic sense.
Conclusion
By establishing NBP as being "as hard as Minkowski," this research provides a new geometric framework for understanding subset-sum variations. It explains the long-standing stagnation in algorithmic improvements for NBP and identifies the specific precision threshold ($2^{\sqrt{n}}/2^n$) where number balancing becomes equivalent to the Shortest Vector Problem. Future work may focus on whether this hardness extends to the "moderately good" regime—solutions that are better than $n^{-\log n}$ but not yet at the exponential threshold required for the current reduction.
Summary updated