The subset sum problem is NP-complete. Given integers, find a subset that sums to a target. Simple to state, exponentially hard to solve.
I built a solver that races 49 engines against every instance - published baselines and original methods - and reports which engine produced the answer.
How it works
Every applicable engine attacks the problem at once. The first to find the answer wins, and the winner is reported. That second part matters: you do not just get an answer, you learn which class of technique solved that class of instance.
Published baselines included for comparison: Schroeppel-Shamir, meet-in-the-middle (Horowitz-Sahni), BCJ, HGJ, ColumnSAT, Bonnetain, bitset DP.
Original engines: GDEP (Goal-Driven Element Partitioning), adaptive core-aware partitioning, and arbitrary-precision (BigUint) paths for values beyond u128.
What the numbers actually are
- n=60, 64-bit: 524 s on an Intel i3-2100 - measured, 1,649x faster than BCJ's published runtime of 864,000 s (10 days)
- n=60 on a Ryzen 9: 24.3 s projected - that would be roughly 35,500x, but it is a projection, not a measurement
- Memory floor: ~12 GB at n=60. Below that the machine thrashes and runs 3-4x slower.
Note: 864,000 is BCJ's runtime in seconds, not a speedup. The ratio is that figure divided by my time.
What this does not claim
- Baselines are quoted from publication, not re-measured on the same machine. A true head-to-head is still outstanding.
- No world records. The 65 categories are categories I defined; they measure coverage of my own suite.
- GPU support is detection only - all computation runs on CPU cores.
Code: https://github.com/rehantheorylab-pixel/zpp-subset-sum-solver
Top comments (0)