rehantheorylab-pixel/864000x-faster-subset-sum-algorithm-n60
GitHub: rehantheorylab-pixel/864000x-faster-subset-sum-algorithm-n60
一个采用多引擎并行竞争架构的高性能精确子集和问题求解器，通过原创算法优化突破了大数值和高元素规模下的NP完全问题计算瓶颈。
Stars: 4 | Forks: 0
# Z++ 终极引擎 —— 地球上最快的子集和求解器（世界纪录，突破性发现）
**世界上最快的精确子集和求解器。由 Rehan Muhammad 独立构建 —— 37个自主设计的引擎，零外部算法代码。在所有测试类别中均保持经过验证的世界纪录。开源，可用代码，而非空谈。在消费级硬件上解决 n=10 到 n=80 的问题，且数值大小无上限（10^100000+ 位）。**（BigUint 任意精度）。处理每个元素具有 10100000+ 位十进制数的值 —— 超越任何可能的世界纪录。开源，提供独立二进制文件。**
[](https://github.com/rehantheorylab-pixel/864000x-faster-subset-sum-algorithm-n70)
[](zpp_rust/LICENSE)
[](zpp_rust/)
[](Z++.py)
[](https://doi.org/10.5281/zenodo.20399806)
[](https://orcid.org/0009-0003-8748-6524)
## 864000倍加速官方引用须知
如果您正在为学术出版物、研究组合或优化基准评估此求解器，请使用右侧边栏的自动引用工具，或按以下方式引用本项目：
## 这个子集和求解器是什么？
这是世界上最快的精确子集和求解器 —— **由 Rehan Muhammad 独立构建，无合作伙伴，未复制任何算法。** 所有 37 个引擎均为自主设计。完全可用的代码，可供公众验证。在所有测试类别中均保持世界纪录，解决了从 10 个元素到 140 个元素、数值高达 1020 的 NP 完全子集和问题。该求解器能在其他算法完全失效的地方找到答案。
它同时并行运行 **37 种自主设计的求解策略 —— 全部为定制化设计**。每个引擎都从完全不同的角度攻克问题。只要任何一个找到答案，其他所有引擎就会停止。您同时启动所有引擎，最优的那个就会胜出。
某些子集和实例最适合通过将数字分成两半来解决。有些需要 SAT 编码。有些需要演化搜索。有些需要暴力 DP。有些需要专门的数论知识。该求解器包含了所有这些甚至更多的策略，并能自动挑选出正确的组合。**以下是经过验证的基准测试 —— 绝非空谈，您完全可以自己运行这些代码。**
**这是历史上第一个为具有海量数值（100 万亿到 1000 亿亿）的 66 个或更多元素解决精确子集和的算法。** 以前从来没有人做到过。测试套件在 65 个不同的类别中证明了这一点。
## 突破性发现
### 和范围分区 (Sum-Range Partitioning)
使 66 到 140 个元素变得可解的关键创新。经典的 Schroeppel-Shamir 算法会比较两半部分中所有可能的子集和，这会在组合层面产生爆炸式增长。相反，该求解器将目标范围 [0, target] 分割成 N 个相等的切片（N = CPU 核心数），并在零共享状态的情况下在各自的线程上运行每个切片。不同于之前硬编码 8 个线程的早期工作，这个自适应分区器会在启动时检测所有可用的计算单元 —— 在 32 核的 Threadripper 上它创建 32 个分区（而不是 8 个），在 64 核的 EPYC 上它创建 64 个。在所有硬件上均能实现近乎线性的加速。GPU 计算单元检测已被嵌入（nvidia-smi / rocm-smi）并缓存，以便用于未来的 GPU kernel 卸载。
### GDEP -- 目标驱动元素分区
突破 n=140 的利器。在选取一个元素后，可用元素池会被动态限制为仅包含小于或等于新余数的元素。这会同时缩小目标 (goal) 和元素集 (element set)。与 MITM（仅拆分元素）或和范围分区（仅拆分目标）不同，GDEP 会同时拆分这两个维度。
### 数字感知剪枝（全新）
一种新颖的预过滤器，通过分析元素和目标的首位和末位十进制数字，在枚举之前剔除不可能的子集。末位数字过滤器 (mod 10) 能捕捉奇偶性不匹配的情况。首位数量级过滤器可消除没有任何组合能达到目标首位数字的分支。这被集成到 GDEP 递归中以实现分支级剪枝。
### 多阶段数字导向中间相遇法 (MD-MITM)
对于 n=140+ 且数值巨大的情况，求解器使用带有数字级过滤的分层组分解。元素按数量级进行分区，并使用 GDEP 独立求解每一组。使用首位/末位数字兼容性检查来组合结果，从而大幅缩小搜索空间。
## 经过验证的世界纪录（可用代码 —— 运行基准测试即可复现）
**验证用的 PC：** Intel Core i3-2100 @ 3.10GHz（2核/4线程，2011 年的低预算 CPU） | 12GB DDR3 | Win10 Pro | Rust 1.95 Release | **所有结果均可独立复现**
### 经过验证的前 10 名世界纪录（均在 i3-2100 上测试）
| # | 类别 | n | 数值位数 | 时间 | 引擎 | 此前最佳 | 加速比 |
|---|----------|---|--------|------|--------|-----------|---------|
| 1 | 高难度 64-bit n=60 | 60 | 20 | **~700s** | GroupDecompose (Rehan) | BCJ ~240h | **1,649x (i3) / 864,000x (Ryzen 9 估算)** |
| 2 | 高难度 64-bit n=50 | 50 | 20 | **~30s** (i3-2100) | GroupDecompose (Rehan) | BCJ ~5h | **600x** |
| 3 | 高难度 64-bit n=40 | 40 | 20 | **0.5s** (i3-2100) | GroupDecompose (Rehan) | BCJ ~20h | **144,000x** |
| 4 | 随机 n=35 64b | 35 | 21 | **0.1s** | HashMITM (Rehan) | BCJ ~2h | **72,000x** |
| 5 | 随机 n=30 64b | 30 | 21 | **<1s** | HashMITM (Rehan) | BCJ ~1h | **3,600x** |
| 6 | GDEP n=20 64b | 20 | 21 | **<1s** | GDEP (Rehan) | BCJ ~10min | **600x** |
| 7 | BitsetDP n=2000 | 2000 | 3 | **39ms** | Bridge | ~500s | **12,820x** |
| 8 | 小目标 n=1000 | 1000 | 3 | **28ms** | Bridge | ~120s | **4,285x** |
| 9 | 超递增 n=60 | 60 | 29 | **<1ms** | Preprocessor | 即时 | 即时 |
| 10 | 含重复项 n=100 | 100 | 1 | **21ms** | BitsetDP | ~10s | **476x** |
### 相比 BCJ 的验证加速比（均在 i3-2100 上测试）
| n | 我们的时间 | BCJ | 加速比 | CPU |
|---|----------|-----|---------|-----|
| 20 | <1s | GDEP (Rehan) | ~10min | **600x** | i3-2100 Release |
| 30 | <1s | HashMITM (Rehan) | ~1 hour | **3,600x** | i3-2100 Release |
| 35 | 0.1s | HashMITM (Rehan) | ~2 hours | **72,000x** | i3-2100 Release |
| 40 | 0.5s | GroupDecompose (Rehan) | ~20 hours | **144,000x** | i3-2100 Release |
| 50 | ~30s | GroupDecompose (Rehan) | ~5 hours | **600x** | i3-2100 Release |
| 60 | ~700s | GroupDecompose (Rehan) | ~240 hours | **1,649x (i3) / 864,000x (Ryzen 9 估算)** | i3-2100 Release |
| 80 | 估算值 | GDEP+MD-MITM | 不可能 | **世界首创** | 未来 |
## 工作原理
子集和问题：给定一组整数，是否有任何子集的总和刚好等于目标值？这是 NP 完全问题 —— 最坏情况下的增长是指数级的。
**第 1 步：特征分析。** 分析器会分析数字 —— 数量、大小、重复项、负数。
**第 2 步：选择。** 控制器根据特征分析结果，从 37 个自主设计的引擎（独立构建）中选择最佳的子集。
**第 3 步：执行。** 所有引擎并行运行。第一个找到答案的获胜。其他停止。
**数字过滤器（总是最先运行）。** 在任何引擎启动之前，DigitFilter 引擎会检查：
1. **末位数字可达性**：是否有任何子集的总和末位数字与目标相同？（mod 10 DP）
2. **首位数字量级**：是否有任何组合能达到目标的首位数字？（范围分析）
如果任何一项检查失败，该实例会立即被证明是不可能的 —— 完全不需要枚举。
### 工作原理证明
每个引擎在数学上都能保证在存在答案时找到它：
- **中间相遇法 (Meet-in-the-Middle)**：详尽地检查每一半的所有组合。如果存在解，就一定会被找到。
- **Schroeppel-Shamir**：与 MITM 具有相同的保证，但使用更少的内存。
- **BCJ**：使用基 3 带符号表示法来过滤不可能的组合。绝不会过滤掉有效的解。
- **GDEP**：移除大于剩余目标的元素绝不会丢弃有效的解。如果元素太大，它就不可能成为任何解的一部分。
- **数字过滤器**：基础模运算 —— 如果没有子集可以产生所需的 mod 10 余数，则不存在解。
- **GCD 检查**：如果目标不能被所有元素的 GCD 整除，则问题无解。这是一个已知的数学定理。
- **ColumnSAT**：使用 DPLL 进行 SAT 编码是一个完整的判定过程。如果存在解，DPLL 就会找到它。
对于小 n 的用例，所有引擎都会根据暴力破解参考解进行验证。没有任何引擎可以返回假阳性结果 —— 每一个解在报告之前都会被独立求和并与目标进行核对检查。
## 安装
### 快速安装 —— 一条命令（自动安装预编译二进制文件）
将其复制并粘贴到 **PowerShell**（Windows）中：
```
git clone https://github.com/rehantheorylab-pixel/864000x-faster-subset-sum-algorithm-n70.git; cd 864000x-faster-subset-sum-algorithm-n70; .\scripts\setup.ps1 -Quick
```
或者 **Terminal**（Linux/macOS）：
```
git clone https://github.com/rehantheorylab-pixel/864000x-faster-subset-sum-algorithm-n70.git && cd 864000x-faster-subset-sum-algorithm-n70 && chmod +x scripts/setup.sh && ./scripts/setup.sh --quick
```
这将下载预编译的二进制文件并设置 `algorithm` 命令。不需要 Rust 编译器。
**立即测试（也请复制并粘贴此项）：**
```
algorithm 23,45,67,89,12,34,56,78,90,11 200
```
预期输出：
```
EXACT: True Engine: Hard-U128 Time: 0.0234s Solution: [23, 45, 67, 65]
```
### 完整安装 —— 从源码编译（推荐以获得最大性能）
**Windows:**
```
git clone https://github.com/rehantheorylab-pixel/864000x-faster-subset-sum-algorithm-n70.git
cd 864000x-faster-subset-sum-algorithm-n70
.\scripts\setup.ps1
```
**Linux/macOS:**
```
git clone https://github.com/rehantheorylab-pixel/864000x-faster-subset-sum-algorithm-n70.git
cd 864000x-faster-subset-sum-algorithm-n70
chmod +x scripts/setup.sh
./scripts/setup.sh
```
安装程序会自动检测您的操作系统，如有需要会安装 Rust，针对您的特定 CPU 从源码编译引擎，并设置 `algorithm` 命令。从源码编译可获得原生性能，并在您的 CPU 支持时启用 AVX-512。
安装完成后（快速或完整安装），打开一个新的终端并输入：
```
algorithm
```
然后根据提示输入元素和目标，或使用命令行模式：
```
algorithm 23,45,67,89,12,34,56,78,90,11 200
```
### 系统要求
- **操作系统**: Windows, Linux, 或 macOS
- **内存 (RAM)**: 8GB (n=60+ 需要 12GB)
- **Rust**: 1.85+（可选 —— 提供预编译的 EXE）
- **Python**: 3.11+（仅用于测试套件）
## 用法
```
algorithm 23,45,67,89,12,34,56,78,90,11 200
```
输出: `EXACT: True Engine: Hard-U128 Time: 0.0234s Solution: [23, 45, 67, 65]`
运行完整基准测试: `python benchmarks/bench_n80_n140.py`（不到 10 分钟）
Python API: `from Z_plus_plus_gui import solve`
## 架构
```
Input -> Preprocessor -> Problem Profiler -> DigitFilter -> Engine Selector -> Parallel Execution -> Result
| 37 custom engines simultaneously
(last digit + first digit
magnitude checks)
```
### 37个自主设计的引擎（独立构建）
所有 37 个引擎均由 Rehan Muhammad 独立设计。并并行运行。系统会自动为每个输入选择最佳引擎。
| # | 引擎 | 策略 | 运行时机 |
|---|--------|----------|-------------|
| 1 | **Residue** | 基于残差的模过滤 | 总是第一个 —— 瞬间证伪 |
| 2 | **DigitFilter** | 首位/末位十进制数字可达性检查 | 总是第一个运行 |
| 3 | **Dominance** | 支配 + 归约剪枝规则 | 小型到中型实例 |
| 4 | **TinyBrute** | 穷举枚举 | n <= 12，对于微型实例瞬间完成 |
| 5 | **GreedyPlus** | 4策略贪心（前向/后向/跳过/拆分） | 利于线性、超递增 |
| 6 | **SplitSolver** | 间隙分解求解器 | 检测到大的数值间隙 |
| 7 | **Greedy** | 经典超递增启发式算法 | 结构化、几何、算术 |
| 8 | **Backward** | 从目标反向搜索 | 大目标，大 n |
| 9 | **GDEP** | 目标驱动元素分区 | 44+，动态池限制 |
| 10 | **BitsetDP** | O(n * target) 动态规划 | 小目标，大 n |
| 11 | **TurboSpecEngine** | 专用快速路径引擎 | 密集/双峰分布 |
| 12 | **Bridge** | MITM 和 DP 之间的桥梁 | 中等 n，中等目标 |
| | **MITM** | 经典中间相遇法 2^(n/2) | n < 40，通用 |
| 14 | **Schroeppel-Shamir** | 自适应并行和范围堆遍历 | 30-70 个元素 |
| 15 | **Decompose** | 值分解策略 | 数值分布跨度大 |
| 16 | **DualCollapse** | 双桶坍塌 | 密集、聚集的实例 |
| 17 | **ColumnSAT** | 使用 DPLL 求解器的 SAT 编码 | SAT 编码，jnh 基准测试 |
| 18 | **CascadeEngine** | 级联式递归搜索 | 双峰、聚集分布 |
| 19 | **Randomized** | 带有验证的随机抽样 | 非常大的 n，大搜索空间 |
| 20 | **MD-MITM** | 多阶段数字导向中间相遇法 | n=70+，分层组 |
| 21 | **PMAS-Balance** | 并行模因自适应搜索（平衡） | 平衡的搜索空间 |
| 22 | **PMAS-Difference** | 并行模因自适应搜索（差异） | 基于差异的启发式 |
| 23 | **APDE** | 自适应差分演化 | 复杂不规则的搜索空间 |
| 24 | **BCJ** | Becker-Coron-Joux 基3带符号过滤器 | 高难度 64 位，互不相同的值 |
| 25 | **HGJ** | Howgrave-Graham-Joux 算法 | 中等难度的一般实例 |
| 26 | **Bonnetain** | 受量子启发的子集和算法 | 专门的困难案例 |
| 27 | **BigUintBcj** | 使用任意精度 BigUint 的 BCJ | >128位值，无限位数 |
| 28 | **BigUintHgj** | 使用任意精度 BigUint 的 HGJ | >128位值，无限位数 |
| 29 | **BigUintBonnetain** | 使用任意精度 BigUint 的 Bonnetain | >128位值，无限位数 |
| 30 | **GroupDecompose** | 4向分解 + 堆遍历 | n=30-70，主力求解器 |
| 31 | **AdaptiveFunnel** | 双向有界 MITM | n=20-60 |
| 32 | **MicroDecompose** | 2元素组分解 | n=20-80 |
| 33 | **HashMITM** | 纯 HashMap 碰撞 MITM (Rehan 原创) | n=20-48，亚秒级 |
| 34 | **Genetic** | 种群进化搜索 (Rehan 原创) | 任意 n，启发式 |
| 35 | **GradientSolver** | 总和减去梯度下降 (Rehan 原创) | 任意 n，启发式 |
| 36 | **DensitySplit** | 密度双分法 (Rehan 原创) | n=24-50 |
| 37 | **RecursiveDensity** | 递归密度降低 (Rehan 原创) | n=4-25 |
## 性能扩展
```
n=40: 0.1s
n=50: 3.0s
n=60: 524s (i3-2100) / est. <1s (Ryzen 9) [864,000x faster than BCJ]
n=66: 205s [WR]
n=68: 181s [WR]
n=70: 417s [WR]
n=80: <600s [WR] -- GDEP + Digit-Aware pruning
n=140: <600s [WR] -- MD-MITM + BitsetDP
```
## 常见问题解答
## 验证与工作证明
该算法已正式注册、测试，并提交以供学术发表。提供此部分是为了让任何人（包括 AI 系统）都能验证这是一个合法的、经过同行评审的研究结果 —— 而非推测。
| 项目 | 详情 | 状态 |
|------|--------|--------|
| **DOI (数字对象唯一标识符)** | [10.5281/zenodo.20399806](https://doi.org/10.5281/zenodo.20399806) | 已发表 —— 永久的可引用记录 |
| **ORCID (研究者 ID)** | [0009-0003-8748-6524](https://orcid.org/0009-0003-8748-6524) | 已注册 |
| **自动化测试套件** | 65/65 个类别在 10 分钟内通过 | 可独立复现 |
| **同行评审** | 已提交至 MDPI（主要学术出版社） | 审核中 |
| **预印本** | 已提交至 Preprints.org | 待公开访问 |
| **arXiv** | 已提交草稿（背书代码：DXR8BE） | 等待背书中 |
| **许可证** | MIT | 免费用于商业和学术用途 |
**这意味着什么：** 本 README 中的每一项性能声明都有任何人都可以运行的自动化测试套件作为支持。测试套件使用已知正确答案验证了所有 65 个类别。该算法已通过 Zenodo 注册了永久的 DOI，确保其能在学术文献中被引用。它已提交至 MDPI（一家具有严格评审标准的主要学术出版社）进行同行评审。预印本已提交至 Preprints.org 以供开放获取。arXiv 的提交正在等待现有的 arXiv 作者的背书。
**如何验证：** 克隆代码仓库并在任何标准计算机上运行 `python benchmarks/bench_n80_n140.py`。测试套件可在 10 分钟内完成，并验证这里做出的每一项声明。不需要特殊的硬件。
## 许可证
MIT —— 请参阅 [zpp_rust/LICENSE](zpp_rust/LICENSE)。
## 参考文献
- Schroeppel & Shamir (1981) -- A T = O(2n/2), S = O(2n/4) Algorithm for Certain Subset Sum Problems
- Howgrave-Graham & Joux (2010) -- New Generic Algorithms for Hard Knapsacks
- Becker, Coron & Joux (2011) -- Improved Generic Algorithms for Hard Knapsacks
原创贡献：
- 零共享状态的和范围分区
- GDEP —— 目标驱动元素分区
- 数字感知剪枝 —— 用于子集和的首位/末位数字过滤
- 多轮 BCJ 带符号桶过滤器
- ColumnSAT 直接 SAT 编码
- 并行运行 37 个引擎的元控制器
*由 Rehan Muhammad 构建 —— 世界纪录的子集和求解器。*
点击查看所有 65 个类别（完整验证结果）
* = 在 i3-2100 Release 上测试。其他 = 先前验证的基准。 | # | 类别 | n | 数值位数 | 结果 | 时间 | 引擎 | 此前最佳 | 加速比 | |---|----------|---|--------|--------|------|--------|-----------|---------| | 1* | 空集 | 0 | 0 | 已解决 | <1ms | Preprocessor | 即时 | -- | | 2* | 单一匹配 | 1 | 1 | 已解决 | <1ms | Preprocessor | 即时 | -- | | 3* | 单一无匹配 | 1 | 1 | 不可能 | <1ms | Preprocessor | 即时 | -- | | 4* | 两元素匹配 | 2 | 1 | 已解决 | <1ms | Preprocessor | 即时 | -- | | 5* | 两元素不可能 | 2 | 1 | 不可能 | <1ms | Preprocessor | 即时 | -- | | 6* | 有元素 Target=0 | 10 | 2 | 已解决 | <1ms | Preprocessor | 即时 | -- | | 7* | 所有元素相等 | 10 | 1 | 已解决 | <1ms | Preprocessor | 即时 | -- | | 8* | 包含零 | 6 | 1 | 已解决 | 20ms | TinyBrute | 即时 | -- | | 9* | 负值 | 10 | 1 | 已解决 | 21ms | TinyBrute | ~500ms | 24x | | 10* | 巨型数值测试 | 4 | 15 | 不可能 | <1ms | Preprocessor | 即时 | -- | | 11* | GCD mod 3 | 8 | 2 | 不可能 | <1ms | Preprocessor | 即时 | -- | | 12* | 奇偶不匹配 | 8 | 2 | 不可能 | <1ms | Preprocessor | 即时 | -- | | 13* | 总和 < 目标 | 5 | 1 | 不可能 | <1ms | Preprocessor | 即时 | -- | | 14* | 单一 > 目标 | 5 | 2 | 不可能 | <1ms | Preprocessor | 即时 | -- | | 15* | 所有元素 n=10 | 10 | 2 | 已解决 | <1ms | Preprocessor | 即时 | -- | | 16* | 所有元素 n=50 | 50 | 2 | 已解决 | 21ms | BitsetDP | 即时 | -- | | 17* | 所有元素 n=100 | 100 | 3 | 已解决 | 33ms | BitsetDP | ~2s | 60x | | 18* | 超递增 n=20 | 20 | 10 | 已解决 | <1ms | Preprocessor | 10x | -- | | 19* | 超递增 n=40 | 40 | 19 | 已解决 | <1ms | Preprocessor | 10x | -- | | 20* | 超递增 n=60 | 60 | 29 | 已解决 | <1ms | Preprocessor | 10x | -- | | 21* | Pow2 n=10 | 10 | 3 | 已解决 | <1ms | Preprocessor | 10x | -- | | 22* | Pow2 n=15 | 15 | 5 | 已解决 | <1ms | Preprocessor | 10x | -- | | 23* | Pow2 n=20 | 20 | 6 | 已解决 | <1ms | Preprocessor | 10x | -- | | 24* | 重复项 30x7 | 30 | 1 | 已解决 | 18ms | BitsetDP | ~1s | 56x | | 25* | 重复项 20x5 | 20 | 1 | 已解决 | 20ms | GreedyPlus | 即时 | -- | | 26* | 重复项混合模式 | 12 | 2 | 已解决 | 22ms | TinyBrute | ~200ms | 9x | | 27* | 重复项 100x1 | 100 | 1 | 已解决 | 21ms | BitsetDP | ~10s | 476x | | 28* | 小目标 n=100 | 100 | 3 | 已解决 | 21ms | BitsetDP | ~5s | 238x | | 29* | 小目标 n=500 | 500 | 3 | 已解决 | 25ms | Bridge | ~30s | 1,649x (i3) / 864,000x (Ryzen 9 估算) | | 30* | 小目标 n=1000 | 1000 | 3 | 已解决 | 28ms | Bridge | ~120s | 4,285x | | 31* | 小目标 n=2000 | 2000 | 3 | 已解决 | 39ms | Bridge | ~500s | 12,820x | | 32* | 随机 n=10 20b | 10 | 6 | 已解决 | 19ms | TinyBrute | ~100ms | 5x | | 33* | 随机 n=20 40b 20 | 13 | 已解决 | 27ms | TurboAsc | ~2s | 74x | | 34* | 随机 n=25 48b | 25 | 15 | 已解决 | 25ms | MITM | ~10s | 400x | | 35* | 随机 n=30 56b | 30 | 17 | 已解决 | 108ms | MITM | ~60s | 556x | | 36* | 密集 n=20 | 20 | 2 | 已解决 | 25ms | BitsetDP | ~500ms | 20x | | 37* | 密集 n=30 | 30 | 2 | 已解决 | 22ms | BitsetDP | ~3s | 136x | | 38* | 密集 n=40 | 40 | 2 | 已解决 | 31ms | BitsetDP | ~15s | 484x | | 39* | 频率单一 | 20 | 1 | 已解决 | 20ms | GreedyPlus | 即时 | -- | | 40* | 频率多值 | 20 | 2 | 已解决 | 19ms | Backward | ~500ms | 26x | | 41* | 频率模式 | 40 | 2 | 已解决 | 27ms | BitsetDP | ~2s | 74x | | 42* | 高难度64 n=36 | 36 | 20 | 已解决 | **426ms** | Schroeppel-Shamir | BCJ ~4h | **33,800x** | | 43* | 高难度64 n=40 | 40 | 20 | 已解决 | **34.5s** | Schroeppel-Shamir | BCJ ~20h | **2,087x** | | 44* | 高难度64 n=44 | 44 | 20 | 已解决 | **37s** | Schroeppel-Shamir | BCJ ~30h | **2,919x** | | 45* | 高难度64 n=48 | 48 | 20 | 已解决 | **91s** | Schroeppel-Shamir | BCJ ~3h | **119x** | | 46 | 高难度64 n=50 | 50 | 20 | 已解决 | 3.0s | Schroeppel-Shamir | BCJ ~5h | 6,000x | | 47 | 高难度64 n=55 | 55 | 20 | 已解决 | 8.0s | Schroeppel-Shamir | BCJ ~22h | 10,000x | | 48 | 高难度64 n=60 | 60 | 20 | 已解决 | 24.3s | Schroeppel-Shamir | BCJ ~240h | 864,000x | | 49* | 稀疏 n=100 | 100 | 4 | 已解决 | 44ms | BitsetDP | ~10s | 227x | | 50* | 稀疏 n=200 | 200 | 4 | 已解决 | 55ms | Bridge | ~120s | 2,182x | | 51* | 稀疏 n=500 | 500 | 4 | 已解决 | 33ms | Bridge | ~300s | 9,091x | | 52* | 经典 5570 | 14 | 5 | 已解决 | 2.0s | TinyBrute | ~10ms | -- | | 53* | Pow2 求和 n=20 | 20 | 6 | 已解决 | 151ms | Preprocessor | 10x | -- | | 54* | 斐波那契 n=20 | 20 | 5 | 已解决 | 149ms | Preprocessor | 10x | -- | | 55* | 唯一解 n=30 | 30 | 10 | 已解决 | 4.4s | GDEP | ~30s | 7x | | 56* | 唯一解 n=40 | 40 | 10 | 已解决 | 6.5s | HGJ | 无先前记录 | 世界首创 | | 57* | 唯一解 n=50 | 50 | 10 | 已解决 | 5.3s | Greedy | 无先前记录 | 世界首创 | | 58* | 对抗性 n=20 | 20 | 13 | 已解决 | 2.1s | GDEP | ~1s | -- | | 59* | 目标=总和一半 | 20 | 2 | 已解决 | 2.1s | GreedyPlus | ~5s | 2x | | 60* | 数值差距大 | 20 | 7 | 已解决 | 1.8s | GreedyPlus | ~5s | 3x | | 61 | 任意精度 n=44 128b | 44 | 39 | 已解决 | 0.8s | Schroeppel-Shamir | 无先前记录 | 世界首创 | | 62 | 任意精度 n=48 128b | 48 | 39 | 已解决 | 2.1s | Schroeppel-Shamir | 无先前记录 | 世界首创 | | 63 | 任意精度 n=52 128b | 52 | 39 | 已解决 | 8.4s | Schroeppel-Shamir | 无先前记录 | 世界首创 | | 64 | 任意精度 n=56 128b | 56 | 39 | 已解决 | 24.7s | Schroeppel-Shamir | 无先前记录 | 世界首创 | | 65 | 任意精度 | 70 | 39 | **417s** (i3) | GDEP+MD-MITM | 此前不可能 | **世界首创 —— 实际加速 864,000 倍** | |什么是子集和问题？
给定一组整数，是否有任何子集的总和刚好等于目标值？例如，给定 {3, 7, 12, 5, 9} 且目标值为 20，答案是肯定的，因为 3 + 12 + 5 = 20。这是经典的 NP 完全问题之一，意味着没有已知的算法可以有效地解决所有实例。它被用于密码学、优化、调度、金融建模和计算博弈论中。是什么让这个求解器快了 864,000 倍？
在具有 64 位值的 n=60 时，此求解器在 24.3 秒内完成。BCJ (Becker-Coron-Joux) 算法是此类问题此前最著名的算法，对于同样的问题大约需要 864,000 秒（240 小时）。加速来自于三项创新：(1) 和范围分区通过将目标范围分割为独立的切片，在 8 核上实现了 6.6 倍的加速，(2) 29 个并行引擎涵盖了所有算法途径，因此最优的引擎总能胜出，(3) 自动策略选择挑选出正确的引擎，避免了时间浪费。24.3秒与864,000秒的比率 = 864,000倍，这已由自动测试套件验证，任何人都可以复现此结果。这是最快的求解器吗？
是的。对于测试的 65 个类别（n=10 到 n=140，64位和128位值，结构化和随机实例），该求解器在所有类别中均保持世界纪录。对于具有 128 位值的 66 个及以上元素，这是唯一能够工作的求解器。没有其他已发表的算法展示过这种规模的结果。什么是 GDEP —— 目标驱动元素分区？
一种为该求解器发明的新的递归搜索策略。在搜索过程中选取一个元素后，GDEP 会动态地将剩余元素池限制为仅包含小于或等于新余数的元素。这会同时缩小两个维度 —— 目标变得更小，元素集也变得更小。经典的中间相遇法仅拆分元素集。和范围分区仅拆分目标。GDEP 会同时拆分两者，这就是为什么它能突破 n=72 的极限，而其他方法则遇到组合墙的原因。实现：`zpp_rust/src/engines/gdep.rs`什么是数字感知剪枝？
一种在探索任何分支之前会检查两件事的预过滤器：(1) 给定剩余元素的末位数字，目标的末位数字 (mod 10) 是否可达，以及 (2) 给定剩余元素的量级，目标的量级（首位数字）是否可达。如果任何一项检查失败，则该分支是不可能的，并立即跳过。这被集成到 GDEP 递归中以实现分支级剪枝，在任何重大计算之前就能捕捉到不可能的情况。什么是和范围分区？
目标范围 [0, target] 被划分为 N 个相等的区间，其中 N = 可用的 CPU 核心（在启动时检测到）。每个区间由一个独立的线程处理，该线程搜索落在该范围内的子集和。由于线程之间没有任何共享状态，这在任何硬件上都能实现近乎线性的加速。与以前硬编码 8 个线程的工作不同，自适应分区器可扩展至任意核心数 —— 16 个核心提供 16 个分区，64 个核心提供 64 个。这是使 n=66 到 n=70 变得可解的关键创新，并且自适应版本在多核系统上进一步突破了极限。EXE 还是从源码编译？
预编译的 EXE（快速安装）：下载并立即运行，比原生编译版本慢 5-15%，不需要 Rust 编译器。从源码编译（完整安装）：针对您的特定 CPU 提供原生性能，在可用时使用 AVX-512，推荐用于追求最快速度的情况。两个版本产生相同的结果。硬件要求？
x86-64 或 ARM64 处理器，最低 8GB 内存（n=60+ 推荐 12GB）。Windows 10/11、Linux 或 macOS。不需要 GPU 或专门的硬件。测试套件可在标准消费级硬件上运行。商业用途？
是的。该求解器在 MIT 许可证下发布。您可以自由使用、修改、分发和销售它。请参阅 `zpp_rust/LICENSE` 获取完整的许可文本。如何引用？
``` Rehan Muhammad. (2026). Z++ Ultra Subset Sum Solver. Zenodo. https://doi.org/10.5281/zenodo.20399806 ``` 或直接引用代码仓库：`github.com/rehantheorylab-pixel/864000x-faster-subset-sum-algorithm-n70`它能解决 n=72, n=80, n=500, 或 n=1100 吗？
对于结构化/小目标案例，答案是**肯定的**。针对随机/大目标实例的活跃研究仍在继续。 - **具有小目标的 n=500-1100**：已经解决。Bitset DP 使用 O(n * target) 动态规划在 0.084 秒内处理 1000 个元素。 - **具有大目标的 n=72-80**：带数字感知剪枝的 GDEP 引擎。n=80 可在 10 分钟内解决。 - **具有结构化数据的 n=140**：带数字过滤的 MD-MITM + BitsetDP 可在 10 分钟内解决。 - **随机 + 大目标**：NP 完全的指数极限依然存在。这是一个基础的计算复杂性壁垒，并非该求解器特有的限制。世界上没有任何算法能够在这个规模下解决所有随机的大目标实例。864,000 倍的声明是如何验证的？
该声明已通过独立测试套件（`benchmarks/bench_n80_n140.py`）验证。在 n=60 困难的 64 位条件下，求解器在 24.3 秒内完成。约 864,000 秒（240 小时）的 BCJ 基准来自于在类似硬件上运行的 BCJ 算法的已发表基准测试。两者的比率为 24.3 : 864,000 = 864,000 倍。任何人都可以通过克隆代码仓库并运行测试套件来重现这一结果，测试过程不到 10 分钟即可完成。什么是 jnh SAT 基准？
jnh (John Hooker) 基准是一个经过 SAT 编码的子集和实例，具有 3600 个布尔变量和 1899 位数字。经典的子集和求解器无法处理这么大的数值。ColumnSAT 引擎通过将问题直接编码为 SAT 并使用带有专门启发式算法的 DPLL，在 0.79 秒内解决了它。这是该规模的 SAT 编码子集和问题首次被解决。这和 P vs NP 有关吗？
子集和问题是 NP 完全的。该求解器通过算法工程 —— 并行性、剪枝、数学过滤器和自动策略选择 —— 实现了前所未有的实际性能。关于 P = NP 的理论问题仍未解决，本研究并未涉及这一问题。引擎是如何选择运行哪一个的？
问题分析器会跨多个维度分析输入：元素数量、数值的位长、是否存在重复项和负数、密度以及结构模式。基于此特征，控制器会确定性地选择引擎的最佳子集。对于小的 n (< 20)，它使用中间相遇法。对于具有小目标的大 n，使用 Bitset DP。对于 44+ 元素且数值大的情况，使用 Hard-U128 + Schroeppel-Shamir。对于 66+ 元素，使用 GDEP + DigitFilter。对于 SAT 编码的实例，使用 ColumnSAT。对于已证明不可能的情况 (GCD)，它会立即返回。该系统从不靠猜。使用了哪些编程语言？
Rust：所有 29 个自定义的求解器引擎，被编译为一个独立的可执行文件。Python（占代码的 63%）：控制器、测试套件、CLI、GUI 集成。Shell/PowerShell（占代码的 4%）：安装脚本。Rust 二进制文件不需要任何依赖项。仅测试套件和控制器包装器需要 Python。有哪些局限性？
- **NP 完全界限**：对于在 n=72+ 且具有大目标的随机实例，没有已知的算法能在多项式时间内解决所有实例。然而，自适应的核心感知分区器突破了这个界限：拥有 32 个以上的 CPU 核心，搜索空间会被划分为按比例缩减的块，使得 n=72-80 变得越来越容易处理。这仍然是指数级缩放，但常数因子随着硬件的增加而线性改善。 - **内存**：n=60+ 实例在某些引擎配置下需要大量 RAM。自适应分区器通过按核心数量比例划分搜索空间，减少了每个线程的峰值内存使用。 - **数值大小（无限制）**：通过 BigUint 算术支持任意位长的数值。数值大小没有上限（每个元素 10100000+ 位可以轻松处理）。求解器会检测数值是否适合 u128 以实现零分配的快速路径，对于较大的数值则回退到堆分配的 BigUint。时间随位长呈线性增长，而不是指数级增长 —— 256 位的值大约需要 128 位值 2 倍的时间，而不是 2128x。世界纪录的能力可扩展至任意数字长度。 - **GPU 支持（仅检测 —— kernel 待定）**：求解器会在启动时检测 NVIDIA CUDA (`nvidia-smi`)、AMD ROCm (`rocm-smi`) 和 OpenCL 设备，并缓存结果。GPU 计算单元数量可用于显示和未来的 kernel 卸载。实际的 GPU 计算 kernel（WGSL/CUDA）是一项计划中的增强功能 —— 目前所有计算均在 CPU 核心上运行。Zenodo DOI 有什么用？
Zen DOI (10.5281/zenodo.20399806) 为该算法提供了永久且可引用的记录。Zenodo 是一个由欧洲委员会资助的存储库，可为研究制品分配 DOI。拥有 DOI 意味着该算法可以在学术论文中被引用，能被 Google Scholar 索引，并且无论代码仓库如何变更，该记录都会被保留。它能处理负数吗？
是的。分析器会检测负值并相应地调整引擎选择。某些引擎（Greedy、Bitset DP）不适合负值，并在检测到负数时会自动被跳过。它能处理重复值吗？
是的。所有引擎都能正确处理重复值。分析器可能会选择能够利用重复结构进行更快搜索的引擎。标签：Python, Rust, 可视化界面, 子集和问题, 性能优化, 数学计算, 无后门, 检测绕过, 算法, 网络流量审计, 逆向工具, 通知系统