标题： 证书敏感子集和：实现实例复杂性 显示英文标题

标题： Certificate-Sensitive Subset Sum: Realizing Instance Complexity

摘要： 我们据知，这是首个针对规范NP完全问题的确定性、证书敏感算法，其运行时间可证明地适应每个输入的结构。 对于一个子集和实例$(S, t)$，令$\Sigma(S)$表示不同的子集和的集合，并定义$U = |\Sigma(S)|$。 这个集合作为信息理论意义上的最小见证，即实例复杂度（IC）证书。 我们的求解器 IC-SubsetSum 以确定性时间$O(U \cdot n^2)$和空间$O(U \cdot n)$枚举$\Sigma(S)$的每一个元素。 一种随机变体实现了期望运行时间$O(U \cdot n)$。 该算法的复杂度因此直接由证书大小决定，这种结构敏感性能与一个保证的最坏情况运行时间$O^*(2^{n/2 - \varepsilon})$相匹配，对于某个常数$\varepsilon > 0$，这是首次在每个实例上严格优于经典方法的结果。 我们重新审视依赖于子集和问题的经典$2^{n/2}$硬度的细粒度归约，并表明这些论证仅在$U$最大化的无冲突实例中成立。 IC-SubsetSum从结构上重新提出了这一障碍，并为NP完全问题中的证书敏感算法引入了一个新范式。 显示英文摘要

摘要： We present, to our knowledge, the first deterministic, certificate-sensitive algorithm for a canonical NP-complete problem whose runtime provably adapts to the structure of each input. For a Subset-Sum instance $(S, t)$, let $\Sigma(S)$ denote the set of distinct subset sums and define $U = |\Sigma(S)|$. This set serves as an information-theoretically minimal witness, the instance-complexity (IC) certificate. Our solver, IC-SubsetSum, enumerates every element of $\Sigma(S)$ in deterministic time $O(U \cdot n^2)$ and space $O(U \cdot n)$. A randomized variant achieves expected runtime $O(U \cdot n)$. The algorithm's complexity is thus directly governed by the certificate size, and this structure-sensitive performance is paired with a guaranteed worst-case runtime of $O^*(2^{n/2 - \varepsilon})$ for some constant $\varepsilon > 0$, the first such result to strictly outperform classical methods on every instance. We revisit fine-grained reductions that rely on the classical $2^{n/2}$ hardness of SubsetSum and show that these arguments hold only for collision-free instances where $U$ is maximal. IC-SubsetSum reframes this barrier structurally and introduces a new paradigm for certificate-sensitive algorithms across NP-complete problems.