Certificate-Sensitive Subset Sum: Realizing Instance Complexity
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911126587965440 |
|---|---|
| author | Salas, Jesus |
| author_facet | Salas, Jesus |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_15511 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Certificate-Sensitive Subset Sum: Realizing Instance Complexity Salas, Jesus Computational Complexity Data Structures and Algorithms F.1.3; F.2.2 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$. |
| title | Certificate-Sensitive Subset Sum: Realizing Instance Complexity |
| topic | Computational Complexity Data Structures and Algorithms F.1.3; F.2.2 |
| url | https://arxiv.org/abs/2507.15511 |