This paper, published in 2016 by researchers at the University of Washington, explores the computational complexity of a classic problem in discrete mathematics: the Number Balancing Problem (NBP). By drawing a deep connection between NBP and the geometry of numbers, the authors show that finding high-quality solutions to number balancing is essentially as difficult as solving some of the most famous hard problems in lattice theory.
TL;DR
The authors prove a bidirectional relationship between the Number Balancing Problem and Minkowski’s Theorem. They demonstrate that an algorithm capable of finding near-optimal subset-sum balances would also provide a polynomial-factor approximation for the Shortest Vector Problem (SVP), a cornerstone of modern cryptography.
What Problem Does This Paper Address?
The Number Balancing Problem (NBP) is a variation of the classic NP-complete Partition Problem. Given a set of $n$ real numbers $a_1, \dots, a_n$ in the interval $[0, 1]$, the goal is to find two disjoint subsets whose sums are as close as possible.
Mathematically, we want to find a vector of "signs" $x \in \{-1, 0, 1\}^n$ (excluding the zero vector) that minimizes the absolute value of the inner product $|\langle a, x \rangle|$.
We know from the pigeonhole principle that a solution always exists where the difference is exponentially small (roughly $O(\sqrt{n}/2^n)$). However, finding this minimum is NP-hard. For decades, the best polynomial-time approach has been the "differencing algorithm" by Karmarkar and Karp (1982), which achieves a sub-exponential error of $n^{-\Theta(\log n)}$. The gap between what we know exists and what we can actually find in polynomial time has remained a major open question.
Methods
The authors bridge this gap by relating NBP to Minkowski’s Theorem, which states that any large enough symmetric convex body must contain a non-zero integer point.
- From Minkowski to NBP: The authors show that if you have an "oracle" (a black-box algorithm) that can find integer points in a symmetric convex body (an approximate Minkowski oracle), you can use it to solve NBP. They construct a specific convex body—a "slab" of a hypercube—and prove that its volume is large enough to guarantee the existence of a balancing vector via Minkowski's Theorem.
- From NBP to Minkowski: This is the more surprising direction. The authors show that a high-quality NBP oracle can be used to find short vectors in a lattice. They use John’s Theorem to approximate any convex body with an ellipsoid and then apply LLL lattice reduction to "regularize" that ellipsoid.
- Recursive Self-Reduction: A key technical innovation is a recursive technique. They show how to take an NBP oracle that finds a "somewhat" balanced solution and repeatedly apply it to smaller sub-problems to eventually find an "extremely" balanced solution. This allows them to transform a standard NBP solver into a tool for finding short vectors in general lattices.
Datasets
This is a theoretical paper in computer science and mathematics. No empirical datasets or benchmarks were used for training or evaluation. The results are established through rigorous mathematical proofs.
Key Insights and Ideas
- The Hardness Gap: The paper suggests that the difficulty of improving upon the Karmarkar-Karp algorithm is not just a lack of ingenuity, but is tied to the fundamental hardness of lattice problems like the Shortest Vector Problem (SVP).
- Geometric Equivalence: NBP is often thought of as a purely combinatorial problem. This paper reframes it as a geometric problem: finding an integer point near a specific hyperplane within a high-dimensional cube.
- Lattice-Based Cryptography Connection: Since many modern cryptographic schemes (like those used for post-quantum security) rely on the hardness of finding short vectors in a lattice, this paper implies that if someone found a "too good" algorithm for number balancing, it could potentially threaten those cryptosystems.
Key Results
- Theorem 1: A $\rho$-approximation for Minkowski’s problem (finding a point in $\rho K$) yields a $\delta$-approximation for NBP, where the error $\delta$ is exponentially small: $2^{-n^{\Theta(1/\rho)}}$.
- Theorem 3: Conversely, any polynomial-time algorithm that guarantees an NBP solution with error at most $2^{\sqrt{n}}/2^n$ would provide an $O(n^5)$-approximation for Minkowski’s problem.
- SVP Hardness: The authors conclude that NBP is essentially as hard as the Shortest Vector Problem in the $L_\infty$ norm.
Limitations and Future Work
- The "High Quality" Requirement: The reduction from NBP to Minkowski requires an NBP oracle with a very small error bound ($\leq 2^{\sqrt{n}}/2^n$). The paper does not definitively prove the hardness of finding "moderately" good solutions—those that are better than Karmarkar-Karp but still much larger than the pigeonhole bound.
- Closing the Gap: A natural next step for researchers is to see if these techniques can be pushed further to show that even achieving an error of, say, $2^{-n^{0.1}}$ is as hard as lattice problems.
- Algorithmic Improvements: While the paper focuses on hardness, the geometric insights might eventually lead to new types of approximation algorithms for NBP that use lattice-based techniques.
Summary updated