2025/07/21 by Salas, Jesus
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.1.3 #F.2.2 #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2507.15511
openalex publication_date 2025/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Subset Sum problem is a classical NP-complete problem with a long-standing O^*(2n/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 ⋅ n2), with a randomized variant achieving expected time O(U ⋅ 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^*(2n/2-ε) time with ε=log2((4)/(3)) - the first unconditional deterministic improvement over the classical O^*(2n/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.