Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.12019 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908412440215552 |
|---|---|
| author | Nkosi, Thami |
| author_facet | Nkosi, Thami |
| contents | This paper presents a deterministic algorithmic approach of exploring the solution space of the Subset Sum Problem. The algorithm presented is input-robust and structurally adaptive. Exploration is guided and narrows into areas in the solution space where solutions are possible, referred to as in-bound solution space, skipping all areas where solutions are impossible. Unfortunately, this can lead to false positives: paths that are hinted to potential have solutions but ultimately realized to not lead to solutions. The in-bound solution space navigated can therefore be filled with only false positives, only true solutions or a mix of the two, affecting the algorithm's performance in different ways. We then detail the challenges of exploring the in-bound solution space for different instances. Further, we show how this algorithm may practically generalize to other NP/NP-complete problems with appropriate adaptation. An introductory discussion is done on this generalization to k-SAT and general CNF-SAT, deferring extensive detail to a follow-up paper. This paper does not satisfy P vs NP proof requirements and does not claim to resolve the problem. However, it has implications for the P vs NP and offers a practical lens through the algorithm of what is feasible with it. The feasibility bounds of the algorithm reveal a nontrivial relationship between decision and counting complexity. To facilitate easy reproducibility, we include in the paper a full C++ implementation of the algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12019 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide Nkosi, Thami Computational Complexity This paper presents a deterministic algorithmic approach of exploring the solution space of the Subset Sum Problem. The algorithm presented is input-robust and structurally adaptive. Exploration is guided and narrows into areas in the solution space where solutions are possible, referred to as in-bound solution space, skipping all areas where solutions are impossible. Unfortunately, this can lead to false positives: paths that are hinted to potential have solutions but ultimately realized to not lead to solutions. The in-bound solution space navigated can therefore be filled with only false positives, only true solutions or a mix of the two, affecting the algorithm's performance in different ways. We then detail the challenges of exploring the in-bound solution space for different instances. Further, we show how this algorithm may practically generalize to other NP/NP-complete problems with appropriate adaptation. An introductory discussion is done on this generalization to k-SAT and general CNF-SAT, deferring extensive detail to a follow-up paper. This paper does not satisfy P vs NP proof requirements and does not claim to resolve the problem. However, it has implications for the P vs NP and offers a practical lens through the algorithm of what is feasible with it. The feasibility bounds of the algorithm reveal a nontrivial relationship between decision and counting complexity. To facilitate easy reproducibility, we include in the paper a full C++ implementation of the algorithm. |
| title | Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2506.12019 |