{"ID":2892206,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.15511","arxiv_id":"2507.15511","title":"Certificate-Sensitive Subset Sum: Realizing Instance Complexity","abstract":"The Subset Sum problem is a classical NP-complete problem with a long-standing $O^*(2^{n/2})$ deterministic bound due to Horowitz and Sahni. We present results at two distinct levels of generality. First (instance-sensitive bound), we introduce, to our knowledge, the first deterministic algorithm whose runtime provably scales with the certificate size $U = |Σ(S)|$, the number of distinct subset sums. Our enumerator constructs all such sums in time $O(U \\cdot n^2)$, with a randomized variant achieving expected time $O(U \\cdot n)$. This provides a constructive link to Instance Complexity by tying runtime to the size of an information-theoretically minimal certificate. Second (unconditional worst-case bound), by combining this enumerator with a double meet-in-the-middle strategy and a Controlled Aliasing technique that enforces a simple canonical-normal-form (CNF) expansion policy on aliased states, we obtain a deterministic solver running in $O^*(2^{n/2-\\varepsilon})$ time with $\\varepsilon=\\log_2(\\frac{4}{3})$ - the first unconditional deterministic improvement over the classical $O^*(2^{n/2})$ bound for all sufficiently large $n$. Finally, we refine fine-grained hardness for Subset Sum by making explicit the structural regime (high collision entropy / near collision-free) implicitly assumed by SETH-based reductions, i.e., instances with near-maximal $U$.","short_abstract":"The Subset Sum problem is a classical NP-complete problem with a long-standing $O^*(2^{n/2})$ deterministic bound due to Horowitz and Sahni. We present results at two distinct levels of generality. First (instance-sensitive bound), we introduce, to our knowledge, the first deterministic algorithm whose runtime provably...","url_abs":"https://arxiv.org/abs/2507.15511","url_pdf":"https://arxiv.org/pdf/2507.15511v6","authors":"[\"Jesus Salas\"]","published":"2025-07-21T11:26:38Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DS\"]","methods":"[]","has_code":false}